Task 49. Мышка и зернышки
UniLecsЗадача: Пол прямоугольной формы выложен плитками 1х1, на каждую из которых высыпано от 0 до K зернышек (K <= 30000). Размеры пола MxN.
Мышка выбегает из верхнего левого угла и двигается к входу в противоложном углу. Мышка может двигаться только вправо или вниз, собирая все зернышки с плитки, на ктр она находится.
Входные данные:
Дана матрица MxN (M,N <= 100). Матрица содержит кол-во зернышек в каждой плитке.
Вывести кол-во зернышек на каждом шаге маршрута мышки, при ктр она соберет наибольшее кол-во зернышек.
Например,
3 2 4
3 2 4
1 5 1
Вывод:
3 3 2 5 1
Идея: Воспользуемся методом динамического программирования. Пусть на плитке (i, j) находится arr[i][j].
Пусть grains[i][j] содержит максимальное количество зернышек, ктр можно собрать при движении из левого верхнего угла в клетку (i,j).
Так как на плитку (i,j) можно попасть или из плитки (i - 1, j) или из (i, j - 1), то получаем формулу:
grains[i][j] = Max(grains[i - 1][j], grains[i][j - 1]) + arr[i][j]
Изначально все ячейки нулевой строки и нулевого столбца массива grains инициализируем -1. Для корректного пересчета значения grains[1][1] следует обнулить одну из ячеек grains[0][1] или grains[1][0]. Тогда мы получим значение ячейки:
grains[1][1] = Max(grains[0][1], grains[1][0]) + arr[1][1] = 0 + arr[1][1].
После проведенных вычислений grains[i][j] уже будет содержать максимальное количество зернышек, которое можно собрать по достижении плитки (i, j). Состояние массива grains по окончанию вычислений:
Реализация:
https://gist.github.com/unilecs/5c3f99c144c6df13516b442378ce80fe
Тест: