Проблемы, которые требуют поиска минимального пути через некоторую область появляются в различных областях информатики. Например, одним из ограничений в проблеме маршрутизации СБИС является минимизация длины провода. Задача Коммивояжера (ЗК) - поиск маршрута продавца по всех городах с возможностью посетить каждый из них только один раз во время пути - один из канонических примеров NP-полной задачи, для решение которой, по всей видимости, потребуется много времени.
В этой задаче рассматривается нахождение минимального пути через сеть пунктов с перемещением во время путешествия только слева направо.
Для заданной матрицы чисел m×n вы должны написать программу, которая вычисляет путь минимального веса. Путь начинается где-нибудь в колонке 1 (первая колонка) и состоит из последовательности шагов, заканчивающийся в колонке n (последняя колонка). Шаг состоит в перемещении из колонки i в соседнюю (по горизонтали или диагонали) колонку i+1 подряд. Первая и последняя строки (строки 1 и m ) матрицы считаются смежными, т. е. матрица "свёрнута" так, что она представляет собой горизонтальный цилиндр. Допустимые шаги показаны ниже.
Весом пути является сумма чисел в каждой из посещённых n клеток матрицы.
Например, два немного отличающихся пути наименьшего веса в матрицах 5×6 показано ниже (разница только в цифрах в нижнем ряду).
Минимальный путь показан для каждой матрицы. Обратите внимание, что путь в матрице справа использует свойство смежности первой и последней строки.
Входные данные состоят из последовательности матрицы спецификаций. Каждая матрица спецификации состоит из строк и столбцов размером m×n - именно в таком порядке по строкам следуют m×n целых чисел, где m - это количество строк и n - это количество столбцов. Числа появляются в строках ввода построчно, то есть, первые n целых чисел составляют первую строку матрицы, вторые n целых чисел составляют вторую строку и так далее. Числа в строке будут отделены друг от друга одним или несколькими пробелами.
Примечание: не гарантируется, что все числа положительные. Вам будет предложено одну или несколько матриц во входном файле. Входные данные завершаются концом файла.
Для каждой спецификации количество строк будет между 1 и 9 включительно, количество столбцов будет между 1 и 100 включительно. Вес пути не будет превышать целое число, представимое переменной с помощью 30 бит.
Две строки должны быть выведены для каждой матрицы спецификации из входного файла, первая строка представляет собой путь минимального веса, а вторая строка является стоимостью минимального пути. Путь состоит из последовательности n целых чисел (разделенных одним пробелом), представляющих строки, которые представляют собой минимальный путь. Если есть больше чем один путь минимального веса, необходимо вывести тот, который является лексикографически наименьшим.