e-olymp
Məsələlər

Однонаправленная ЗК

Однонаправленная ЗК

Проблемы, которые требуют поиска минимального пути через некоторую область появляются в различных областях информатики. Например, одним из ограничений в проблеме маршрутизации СБИС является минимизация длины провода. Задача Коммивояжера (ЗК) - поиск маршрута продавца по всех городах с возможностью посетить каждый из них только один раз во время пути - один из канонических примеров NP-полной задачи, для решение которой, по всей видимости, потребуется много времени.

В этой задаче рассматривается нахождение минимального пути через сеть пунктов с перемещением во время путешествия только слева направо.

Для заданной матрицы чисел m×n вы должны написать программу, которая вычисляет путь минимального веса. Путь начинается где-нибудь в колонке 1 (первая колонка) и состоит из последовательности шагов, заканчивающийся в колонке n (последняя колонка). Шаг состоит в перемещении из колонки iв соседнюю (по горизонтали или диагонали) колонку i+1подряд. Первая и последняя строки (строки 1 и m ) матрицы считаются смежными, т. е. матрица "свёрнута" так, что она представляет собой горизонтальный цилиндр. Допустимые шаги показаны ниже.

prb3472-1

Весом пути является сумма чисел в каждой из посещённых n клеток матрицы.

Например, два немного отличающихся пути наименьшего веса в матрицах 5×6 показано ниже (разница только в цифрах в нижнем ряду).

prb3472-2

Минимальный путь показан для каждой матрицы. Обратите внимание, что путь в матрице справа использует свойство смежности первой и последней строки.

Входные данные

Входные данные состоят из последовательности матрицы спецификаций. Каждая матрица спецификации состоит из строк и столбцов размером m×n - именно в таком порядке по строкам следуют m×n целых чисел, где m - это количество строк и n - это количество столбцов. Числа появляются в строках ввода построчно, то есть, первые n целых чисел составляют первую строку матрицы, вторые n целых чисел составляют вторую строку и так далее. Числа в строке будут отделены друг от друга одним или несколькими пробелами.

Примечание: не гарантируется, что все числа положительные. Вам будет предложено одну или несколько матриц во входном файле. Входные данные завершаются концом файла.

Для каждой спецификации количество строк будет между 1 и 9 включительно, количество столбцов будет между 1 и 100 включительно. Вес пути не будет превышать целое число, представимое переменной с помощью 30 бит.

Выходные данные

Две строки должны быть выведены для каждой матрицы спецификации из входного файла, первая строка представляет собой путь минимального веса, а вторая строка является стоимостью минимального пути. Путь состоит из последовательности n целых чисел (разделенных одним пробелом), представляющих строки, которые представляют собой минимальный путь. Если есть больше чем один путь минимального веса, необходимо вывести тот, который является лексикографически наименьшим.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10
9 10
Çıxış verilənləri #1
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19