Slink#3021
Slitherlink — це головоломка, яку публікує Nikoli, японська компанія, що популяризувала Судоку. Головоломки Slitherlink набирають популярності, і книжки з такими головоломками почали з'являтися по всьому світу. Правила головоломки прості для розуміння, але розв'язати її буває складно. Кожна головоломка — це прямокутна сітка з точок, які утворюють набір клітинок, кожна з яких або порожня, або містить ціле число від до . Завдання полягає в тому, щоб з'єднати точки відрізками так, щоб утворити цикл (зв'язний шлях, у якого в кожній вершині рівно дві інцидентні ребра), причому в кожній клітинці з числом повинна бути рівно така кількість інцидентних ребер, яка зазначена в клітинці. Для клітинок без числа кількість інцидентних ребер може бути будь-якою. Коректна головоломка Slitherlink завжди містить достатньо непорожніх клітинок, щоб гарантувати єдиний розв'язок. Нижче наведено приклад головоломки Slitherlink і її розв'язку з сайту Nikoli.
Таке завдання, як показав Такаюкі Ято з Токійського університету, у загальному випадку є NP-повним. (Якщо ви не знайомі з цим терміном, неформально це означає, що не існує "ефективного" алгоритму для розв'язання задачі.) Однак, з невеликою модифікацією та застосуванням простих евристик програмне розв'язання можливе. Наша нова головоломка, яку ми назвемо Slink, відрізняється від Slitherlink лише тим, що в ній не може бути порожніх клітинок. Тобто у кожній клітинці обов'язково повинно бути вказано кількість інцидентних ребер. Нижче наведено попередню головоломку Slitherlink, перетворену на Slink (додані числа показані сірим кольором). Зверніть увагу: розв'язок не змінюється, змінюється лише інформація, яка надається у самій головоломці.
Евристики для розв'язання Slink випливають із її структури. Наприклад, розгляньмо клітинку з нулем. У ній не повинно бути жодного інцидентного ребра, тож усі ребра біля нулів можна одразу виключити з розгляду як частину розв'язку. Тепер уявімо трійку поруч із нулем. Оскільки всі ребра біля нуля виключені, спільне ребро між трійкою й нулем також виключається. Це залишає біля трійки лише три ребра, отже саме ці три ребра мають бути частиною розв'язку. Наведена нижче таблиця ілюструє набір евристичних правил, які потрібно правильно застосувати для розв'язання головоломки Slink. Символи «x» між вершинами позначають ребра, які не входять до розв'язку, а відрізки між вершинами означають ребра, що формують частину вирішення. Сірі елементи — це шаблон, на якому ґрунтується правило; чорні елементи вказують додаткові ребра, які потрібно включити або виключити, якщо знайдено таку конфігурацію. Зверніть увагу, що зображені приклади наведені лише для демонстрації і не ілюструють усі можливі варіанти зазначеного правила!
Вхідні дані цієї задачі складаються з набору головоломок Slink, які необхідно розв'язати. У першому рядку вхідних даних для однієї головоломки Slink записано два цілі числа і , розділених пробілом: кількість рядків і стовпців у головоломці. Далі йдуть рядків, кожен з яких містить чисел, розділених пробілами, від до , і задають наповнення головоломки. Мінімальний розмір головоломки — на клітинки, максимальний — на клітинок. Гарантується, що для кожної головоломки у вхідних даних існує єдиний розв'язок, який можна визначити наведеними правилами, якщо кожне правило завжди застосовується, коли це можливо. Рядок з нулями для та означає кінець вхідних даних.
Вихідними даними для цієї задачі є графічне представлення розв'язку головоломки Slink. Перша задача має номер , друга — тощо. Виведіть у окремому рядку номер задачі, далі — розв'язок саме у тому форматі, що продемонстровано нижче. Вертикальні ребра зображуйте символом вертикальної риски '|', горизонтальні ребра — дефісом '-', вершини, у яких шлях змінює напрямок, — знаком плюс '+', а числа у клітинках завжди з пробілом ліворуч і праворуч. Крім того, обраміть увесь вихідний блок рамкою з символів решітки '#' так, щоб число у верхньому лівому куті головоломки знаходилося на чотири позиції правіше від рамки і на три позиції нижче, а число у правому нижньому куті — на чотири позиції лівіше від рамки і на три позиції вище.
Приклад 1