Замощення доміно
У цій задачі вам потрібно перетворити одне замощення прямокутника доміно на інше, переміщуючи доміно по циклах.
Розгляньмо прямокутну сітку розміру h × w. Доміно — це прямокутний блок, який можна розмістити на будь-які дві сусідні клітинки сітки. Замощенням сітки називається такий набір доміно, при якому кожна клітинка покрита рівно одним доміно. Зазначимо, що доміно не можуть виходити за межі сітки.
Вам дано два замощення сітки: початкове і кінцеве. Ваше завдання — перетворити початкове замощення на кінцеве. Для цього ви можете виконувати ходи. Один хід полягає у виборі циклу доміно і переміщенні вздовж цього циклу (формальне визначення наведено нижче). Вартість кожного ходу дорівнює кількості клітинок у відповідному циклі доміно. Загальна вартість трансформацій — це сума витрат на всі виконані вами ходи. Звісно, загальна вартість повинна бути мінімально можливою.
Тепер перейдемо до деталей.
Визначимо цикл доміно додатної довжини n на заданому замощенні. Розгляньмо циклічну послідовність 2n різних клітинок таку, що будь-які дві сусідні клітинки послідовності мають спільну сторону. "Циклічна" означає, що перша і остання клітинка послідовності вважаються сусідніми. Отже, є 2n пар послідовних клітинок у такій послідовності. Покриємо n пар клітинок n неперетинними доміно і отримаємо цикл доміно.
Переміщення доміно вздовж циклу змінює замощення. Спочатку n доміно, що покривають усі 2n клітинок, які належать циклу, видаляються. Потім n нових неперетинних доміно додаються для покриття n інших пар послідовних клітинок. Результуючий набір доміно також є замощенням. Нагадаємо, що вартість такого ходу дорівнює 2n.
Вхідні дані
Перший рядок містить два цілі числа h і w (1 ≤ h, w ≤ 100): висоту і ширину прямокутної сітки.
Кожен з наступних h рядків містить w символів і описує початкове замощення. Кожен символ є одним з наступних:
символ “l” вказує на ліву частину доміно,
символ “r” вказує на праву частину доміно,
символ “u” вказує на верхню частину доміно,
символ “d” вказує на нижню частину доміно.
Наступний рядок містить w знаків тире (“-”).
Кожен з наступних h рядків містить w символів і описує кінцеве замощення в тому ж форматі.
Гарантується, що вхідні дані коректні:
h і w вибрані таким чином, що замощення сітки h× w можливе
кожен символ у кожному замощенні гарантовано має відповідного сусіда в потрібному напрямку
Вихідні дані
У першому рядку виведіть два числа: m - кількість ходів, і p - загальну вартість перетворень. Хоча вартість p повинна бути мінімальною, кількість ходів m може бути довільною.
Наступні m рядків повинні описувати ходи, по одному в рядку. Хід вздовж циклу доміно, що складається з k клітинок, слід записати у вигляді k r_1 c_1 r_2 c_2 ... r_k c_k. Тут r_i і c_i - координати i-ої клітинки циклу. Числа в рядку слід розділяти одним або кількома пробілами. Цикл можна починати в будь-якій точці і проходити в будь-якому напрямку.
Приклади
Примітка
У першому прикладі найменша загальна вартість дорівнює 10. Її можна досягти одним ходом, який включає в себе 10 граничних клітинок сітки в циклічному порядку. П'ять доміно, що покривають клітинки (1, 1) і (1, 2), (1, 3) і (1, 4), (2, 4) і (3, 4), (3, 3) і (3, 2), (3, 1) і (2, 1) прибираються. Після чого додаються нові доміно, що покривають клітинки (1, 2) і (1, 3), (1, 4) і (2, 4), (3, 4) і (3, 3), (3, 2) і (3, 1), (2, 1) і (1, 1).
Рішення показано зліва на рисунку. Зазначимо, що існують і інші способи досягти кінцевого замощення. Справа показано не оптимальне рішення.
У другому прикладі найменша загальна вартість дорівнює 12. Її можна досягти, переміщуючи доміно по трьох малих циклах, кожен з яких складається з чотирьох клітинок. Рішення показано нижче.
