На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
В первую очередь напишем функции хода одного кролика и одного хомяка. Чтобы не задумываться о параметрах для передачи в них, можно все основные данные объявить глобальными.
Для вычисления пути кролика не требуется никаких специальных алгоритмов, достаточно лишь вычислять максимум (а точнее индексом максимального элемента).
Для вычисления пути хомяка требуется воспользоваться динамическим программированием. Заведём массив dp, в котором будем хранить максимальное количество, которое можно собрать, если оптимально двигаться из этой клетки. А это значит, что
dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + mm[i][j]
с учётом крайних случаев. То есть заполнять этот массив надо будет снизу вверх. А дальше обратным ходом (против направления динамики) вычисляем сам путь. И, как это часто бывает, эта часть функции длиньше, чем сама динамика.
Имея все функции, основная программа становится вполне очевидной.
Обе функции работают за время O(N * M). Хотя rabbit и можно переписать так, чтобы было O(N), в данном случае это не скажется на итоговой асимптотике, которая равна O(N * M^2).
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.