Задача. Super Mario
Итак, в левом верхнем углу матрицы размером N*M находится персонаж Супер-Марио. На каждой клетке матрицы разлито некоторое количество кислоты. Супер-Марио может перемещеаться вправа или вниз, а дойти нужно до правого нижнего угла матрицы.
Кислота наносит урон здоровью персонажа Супер-Марио, поэтому важно преодолеть путь с наименьшим уроном.
Определите минимально возможное количество урона, которое получит Супер-Марио.
Входные данные: matrix - числовая матрица, размер матрицы от 1 до 1000 элементов. Элементы матрицы - натуральные числа от 0 до 1000.
Разбор
Воспользуемся методом динамического программирования. Пусть d[i, j] - величина наименьшего урона, которое Супер Марио может получить при проходе от клетки (0, 0) к клетке (i, j).
- d[0, 0] = matrix[0, 0]
- d[i, 0] = d[i - 1, 0] + matrix[i, 0] (идем вниз по столбцу)
- d[0, j] = d[0, j - 1] + matrix[0, j] (идем вправо по строке)
Очевидно, что в клетку (i, j) можно попасть из клетки (i - 1, j) или из клетки (i, j - 1). Так как нам нужно минимизировать урон, то получаем следующую формулу.
d[i, j] = Min(d[i - 1, j], d[i, j - 1]) + matrix[i, j]
Тогда минимальный урон по маршруту (0, 0) - (rows - 1, cols - 1) будет равен значению d[rows - 1, cols - 1].