Задачи
Путь в матрице
Путь в матрице
Задана матрица размером n × m, содержащая неотрицательные целые числа, не превышающие 10000.
Соседние клетки матрицы – это клетки, номера столбцов или строк которых отличаются на 1. Путь от одной клетки матрицы до другой проходит только через соседние клетки.
Найти путь минимальной стоимости между левым верхним и правым нижним углами матрицы. Стоимость пути формируется как сумма элементов матрицы, через которые проходит путь. Разрешается двигаться в соседние клетки влево, вправо, вверх и вниз.
Входные данные
В первой строке содержатся числа n и m (1 ≤ n, m ≤ 10). Далее идет n строк, в каждой строке по m чисел, разделенных пробелом.
Выходные данные
Выведите стоимость минимального пути.
Входные данные #1
4 5 1 9 4 5 9 1 8 1 1 1 1 1 1 9 1 6 5 9 8 1
Выходные данные #1
10