Детектор ігрових рівнів#3322
Олекс — розробник ігор, який працює над головоломкою з процедурно генерованими лабіринтами. В грі є різних конфігурацій рівнів, пронумерованих від до d - 1. Кожен рівень є сіткою розміром w \times h, де кожна клітинка є або стіною (чорною), або проходом (білим). Всі конфігурації рівнів різні (тобто будь-які два рівні відрізняються хоча б однією клітинкою).
Олексу потрібно написати ШІ, який з'являється у верхній лівій клітинці рівня і повинен швидко визначити, на якій конфігурації рівня він знаходиться. ШІ виконує програму, написану на специфічній мові сценаріїв, описаній нижче.
Мова сценаріїв для ШІ складається з наступних команд:
U, D, L, R — команди руху. ШІ рухається на одну клітинку вгору, вниз, вліво або вправо відповідно. Якщо команда руху переміщує ШІ за межі сітки, програма завершується з помилкою.
( <subprogram_path> : <subprogram_wall> ) — умовний оператор. ШІ перевіряє тип клітинки, на якій він знаходиться. Якщо це прохід (білий), виконується <subprogram_path>, інакше виконується <subprogram_wall>.
0, 1, …, 9 — команди ідентифікації рівня. ШІ повинен виконати одну з цих команд, коли він знає, на якому рівні він знаходиться. Після такої команди програма завершується.
Кожна команда руху займає одну одиницю часу для виконання. Виконання умовного оператора та команд ідентифікації рівня є миттєвим.
Олекс хоче програму, яка завжди працює правильно. Тобто, якщо ШІ з'являється на рівні , то виконання програми має завершитися командою i.
Задано набір конфігурацій рівнів, розробіть правильну програму для ШІ, таку, щоб її час виконання в найгіршому випадку був мінімальним.
Перший рядок містить три цілі числа , та (1 \le d \le 10; 1 \le h, w \le 10) — кількість конфігурацій рівнів, висота та ширина кожного рівня.
Решта вхідного файлу містить описів рівнів. Кожен опис складається з рядків довжиною . Усі символи є або B, або W, що представляють стіну (чорну) або прохід (білий) відповідно.
Опис рівнів подано в порядку від до d - 1. Описання розділені порожнім рядком.
Поверніть правильну програму для ШІ з мінімально можливим часом виконання в найгіршому випадку. Якщо існує декілька можливих програм, виведіть будь-яку з них.
Усі пробіли ігноруються під час розбору програми.
ШІ має відрізняти дані конфігурації рівнів у прикладі.
Приклад 1