Дан двумерный массив, заполненный положительными числами. Из каждой клетки массива мы можем двигаться вверх, вниз, влево и вправо.
Наша задача — пройти из левой верхней вершины в правую нижнюю. При этом необходимо минимизировать сумму элементов, которые мы проходим, перемещаясь по матрице.
const grid = [ [1, 2, 3, 9, 7, 2], [7, 2, 8, 4, 6, 6], [8, 1, 3, 2, 5, 3], [3, 3, 3, 4, 5, 1], ]; minPath(grid) === 20
Минимальная сумма элементов составит 20, а оптимальный путь выглядит так:
[ [1, 2, ×, ×, ×, ×], [×, 2, ×, ×, ×, ×], [×, 1, 3, 2, 5, 3], [×, ×, ×, ×, ×, 1], ];
Функция minPath возвращает сумму элементов самого оптимального пути из левой верхней в правую нижнюю вершину.