1 (Отправить) Имя
1 (Отправить)
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Задана матрица натуральных чисел A[1..N, 1..M], m<=n. За каждый проход tчерез клетку (i, j) взимается штраф A[i, j]. Необходимо определить путь с минимальным суммарным штрафом, с которым можно пройти из клетки (1, 1) в клетку (n, m). При этом из текущей клетки можно переходить в любую из 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
8
1 1
2 1
3 2
Задача
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
