Miss M and the Flowers#239

Miss M and the Flowers (Editorial)

Розберемося, що обмежує кількість проходів.

Робот іде з лівого верхнього кута в правий нижній лише вниз і вправо, тому його маршрут завжди проходить рівно через $n + m - 1$ клітинку. За кожен прохід він збирає всі квіти зі свого маршруту, а щоб прохід узагалі відбувся, він має зірвати хоча б одну квітку — тобто маршрут мусить містити хоч одну клітинку, де квітка ще залишилась.

Перший прохід «витрачає» $n + m - 1$ n + m - 1 клітинку. Після нього незайманими лишаються $nm - (n + m - 1)$ nm - (n + m - 1) клітинок. Кожен наступний прохід прибирає щонайменше одну нову клітинку, тому проходів не більше ніж

1 + (nm - (n + m - 1)) = nm - n - m + 2.

1 + \bigl(nm - (n + m - 1)\bigr) = nm - n - m + 2.

Ця межа досяжна: оскільки нас просять максимальну кількість проходів, робот щоразу обирає маршрут, який зачіпає рівно одну ще не обірвану клітинку, і витрачає квіти якнайповільніше.

Отже, відповідь — $nm - n - m + 2$ nm - n - m + 2, або, що те саме, $(n - 1) (m - 1) + 1$ (n-1)(m-1) + 1.

Перевірте окремий випадок $n = 1$ n = 1 чи $m = 1$ m = 1: маршрут тоді єдиний, і формула дає рівно один прохід.

n + m - 1

nm - (n + m - 1)

1 + (nm - (n + m - 1)) = nm - n - m + 2.

nm - n - m + 2

(n - 1) (m - 1) + 1

n = 1

m = 1