#2. Минимальный
#2. Минимальный штраф - 2
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Задана матрица натуральных чисел A[1..N, 1..M]. За каждый проход через клетку (i, j) взимается штраф A[i, j]. Необходимо определить путь с минимальным суммарным штрафом, с которым можно пройти из некотрой клетки первой строки в некоторую клетку N-ой строки. При этом из текущей клетки можно переходить в любую из 3-х соседних клеток, стоящих в строке с номером, на 1 большим текущего номера строки.
Формат входных данных
Первая строка входного файла содержит числа N и M (1<=N, M<=100). Далее идет N*M натуральных чисел A[i, j] (1<=A[i, j]<=100)
Формат выходных данных
Первая строка выходного файла должна содержать штраф. В каждой из следующих N строк должны быть записаны два числа xi, yi -- i-ая клетка искомого пути.
Пример входного файла Пример выходного файла
3 2
2 1 3 4 2 3
6
1 2
2 1
3 1
Способы нахождения
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
