e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
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