Ось ми знову (реліанси)
Гореліани — войовнича раса, яка подорожує всесвітом, завойовуючи нові світи заради розваги. Через їхню жорстоку та веселу натуру, захист життя їхніх лідерів стає серйозним завданням. У рамках плану безпеки гореліан щодня змінюються схеми руху в їхніх містах, а також прокладаються маршрути для всіх гореліанських урядових чиновників до урядової будівлі найшвидшим шляхом.
На щастя для гореліанського міністра транспорту (тобто для вас), всі гореліанські міста спроектовані у вигляді прямокутної сітки кварталів, де кожен квартал є квадратом розміром 2520 рел на сторону (рел — це офіційна одиниця відстані у гореліан). Обмеження швидкості між двома сусідніми перехрестями завжди постійне і може варіюватися від 1 до 9 рел за бліп (бліп, звісно, є офіційною одиницею часу у гореліан). Оскільки гореліани заборонили десяткові числа як нечестиві (якщо ви домінуюча сила у відомому всесвіті, ви можете заборонити що завгодно), обмеження швидкості завжди мають цілісні значення. Це пояснює, чому гореліанські квартали мають довжину рівно 2520 рел: 2520 — це найменше спільне кратне чисел від 1 до 9. Таким чином, час, необхідний для переміщення між двома сусідніми перехрестями, завжди є цілим числом бліпів.
У всіх гореліанських містах урядове житло завжди знаходиться в північно-західному куті міста, а урядова будівля — в південно-східному куті. Вулиці між перехрестями можуть бути односторонніми або двосторонніми, або навіть закритими на ремонт (все це втручання в схеми руху викликає безліч аварій). Ваше завдання, враховуючи деталі обмежень швидкості, напрямків руху та закриття вулиць для гореліанського міста, — визначити найшвидший маршрут від урядового житла до урядової будівлі. (Можливо, через напрямки руху та закриття вулиць, жодного маршруту не існує, в цьому випадку оголошується тимчасовий вихідний день для гореліанських чиновників, і вони беруть вихідний.)
На рисунку вище показано гореліанське місто з позначеними обмеженнями швидкості, односторонніми вулицями та однією закритою вулицею. Передбачається, що рух по вулицях завжди здійснюється з точною швидкістю, вказаною на знаку, і що поворот на куті займає нуль часу. За цих умов ви повинні визначити, що найшвидший маршрут від урядового житла до урядової будівлі в цьому місті становить 1715 бліпів. І якщо наступного дня єдина зміна полягає в тому, що закрита дорога відкривається для двостороннього руху з обмеженням швидкості 9 рел за бліп, найшвидший маршрут стає 1295 бліпів. З іншого боку, припустимо, що три односторонні вулиці переключаються з південного напрямку на північний (при цьому закрита дорога залишається закритою). У цьому випадку жодного маршруту не буде, і день буде оголошено вихідним.
Вхідні дані
Вхідні дані складаються з набору міст, для яких ви повинні знайти найшвидший маршрут, якщо він існує. Перший рядок вхідних даних для кожного випадку містить два цілі числа, які представляють кількість вертикальних і горизонтальних кварталів міста відповідно. Найменше місто складається з одного кварталу, або 1 на 1, а найбільше місто — з 20 на 20 кварталів. Решта частина вхідних даних вказує обмеження швидкості та напрямки руху для вулиць між перехрестями, по одному рядку вуличних сегментів за раз. Перший рядок вхідних даних (після рядка з розмірами) містить дані для найпівнічніших східно-західних вуличних сегментів. Наступний рядок містить дані для найпівнічнішого ряду північно-південних вуличних сегментів. Потім наступний рядок східно-західних вулиць, потім північно-південних вулиць і так далі, до найпівденнішого ряду східно-західних вулиць. Обмеження швидкості та напрямки руху вказуються в порядку із заходу на схід і складаються з цілого числа від 0 до 9, що вказує обмеження швидкості, і символу, що вказує, в якому напрямку може рухатися транспорт. Нульове обмеження швидкості означає, що дорога закрита. Всі цифри і символи розділені одним пробілом. Для східно-західних вулиць символом буде зірочка '*', яка вказує, що рух дозволено в обох напрямках, символ менше '<', який вказує, що рух дозволено тільки в напрямку зі сходу на захід, або символ більше '>', який вказує, що рух дозволено тільки в напрямку із заходу на схід. Для північно-південних вулиць зірочка знову вказує, що рух дозволено в будь-якому напрямку, мала літера "v" вказує, що рух дозволено тільки в напрямку з півночі на південь, а символ каретки '^' вказує, що рух дозволено тільки в напрямку з півдня на північ. Нульова швидкість, що вказує на закриту дорогу, завжди супроводжується зірочкою. Вхідні дані міст продовжуються таким чином, поки не буде вказано значення нуль для обох вертикального і горизонтального розмірів.
Вихідні дані
Для кожного вхідного сценарію виведіть рядок, що вказує ціле число бліпів найкоротшого маршруту, пробіл, а потім слово "бліпів". Для сценаріїв, в яких немає маршруту, виведіть рядок зі словом "Вихідний".