Проблеми, які вимагають пошуку мінімального шляху через деяку область з'являються у різних областях інформатики. Наприклад, одним з обмежень у проблемі маршрутизації НВІС є мінімізація довжини провідника. Задача Комівояжера (ЗК) - пошук маршруту продавця по усіх містах з можливістю відвідати кожне з них лише один раз на своєму шляху - один з канонічних прикладів 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 цілих чисел (відокремлених одним пропуском), що подають рядки, які є мінімальними шляхами. Якщо є більше ніж один шлях мінімальної ваги, необхідно вивести той, який є лексикографічно найменшим.