Перевезення вантажів
Завдання, яке на перший погляд здається простим, як-от перевезення вантажу з точки A до точки B, іноді може бути дуже складним! Системи GPS можуть бути дуже корисними для пошуку маршрутів, але зазвичай не враховують усі фактори. Наприклад, чи враховують вони очікування на світлофорах, коли шукають найшвидший маршрут? А як щодо заторів? Можливо, ви зможете написати кращу програму? У цій задачі вам буде надано карту вулиць, що містить дороги, пронумеровані перехрестя (зі світлофорами) та два склади. Ваше завдання - знайти найшвидший маршрут для перевезення вантажівки зі складу A до складу B. Карти вулиць завжди намальовані на сітці та виглядають так: дивіться малюнок. Сусідство на цій карті визначається як сусідство на північ, південь, схід або захід. Єдині символи, що з'являються на карті, такі: • Символ # позначає клітинку дороги, по якій можуть їздити вантажівки. Дороги межують максимум з двома іншими клітинками дороги, перехрестя або складу. • Одна цифра [0-9] позначає перехрестя, яке контролюється світлофором. Перехрестя межують щонайменше з трьома клітинками дороги. Перехрестя пронумеровані послідовно: жодна цифра не з'явиться, якщо всі невід'ємні цілі числа менші за неї не з'являться на карті. Поведінка світлофорів буде описана нижче. • Точно один символ A позначає місце розташування складу, звідки починають ваші вантажівки. • Точно один символ B позначає місце розташування складу, куди ви хочете доставити ваш вантаж. • Символ . - це просто трава. Ви не можете їздити по ній. У вас є одна вантажівка, яка починає рух зі складу A, і ви намагаєтеся довезти її до складу B згідно з наведеними нижче правилами. Для простоти ми також можемо дискретизувати час на атомарні одиниці або ходи. • За один хід ви можете перемістити вантажівку на сусідню клітинку дороги, перехрестя або складу, або просто залишитися на тій самій клітинці. • Вантажівка може рухатися на клітинку перехрестя лише тоді, коли світлофор для перехрестя зелений у напрямку, з якого вантажівка в'їжджає під час цього ходу. Однак вантажівка на клітинці перехрестя може виїхати в будь-якому напрямку в будь-який час. Перехрестя зі світлофорами періодично дозволяють рух або в напрямку схід-захід, або в напрямку північ-південь, але не обидва одночасно. Вони описуються початковим напрямком і двома числами, що вказують на періоди руху в напрямках схід-захід і північ-південь відповідно. Наприклад, перехрестя, яке спочатку зелене в напрямку північ-південь, описане як "2 3", матиме зелене світло, спрямоване на північ і південь на ходах 1-3 включно, спрямоване на схід і захід на ходах 4-5, і знову на північ і південь на ходах 6-8 тощо.
Вхідні дані
Вхідний тестовий файл міститиме кілька випадків. Кожен тестовий випадок починається з одного рядка, що містить два цілі числа, m і n, розділені пробілами. Карта вулиць складається з m рядків (схід-захід) і n стовпців (північ-південь) клітинок сітки (2 <= m, n <= 20). Наступні m рядків містять n символів кожен, які описують карту за допомогою символів, визначених у наведеній вище постановці задачі. Для кожного пронумерованого перехрестя, що з'являється на карті, у порядку зростання, починаючи з 0, буде рядок тексту з номером перехрестя, за яким слідує символ '-' або '|' і два цілі числа, ai і bi (1 <= ai, bi <= 100), тривалість (у ходах) періодів руху в напрямках схід-захід і північ-південь відповідно. Символ '-' вказує на те, що світлофор спочатку зелений у напрямку схід-захід, тоді як символ '|' вказує на те, що він спочатку зелений у напрямку північ-південь. Порожній рядок відокремлює вхідні тестові випадки, як показано в наведеному нижче прикладі. Один рядок з числами "0 0" позначає кінець введення; не обробляйте цей випадок. Output
Для кожного тестового випадку ваша програма повинна вивести одне ціле число в одному рядку: мінімальну кількість ходів, необхідних для перевезення вашої вантажівки зі складу A до складу B. Якщо дістатися до складу B неможливо, виведіть одне слово "неможливо".
(У другому прикладі насправді швидше скористатися нижнім маршрутом, ніж верхнім. Однак ваша вантажівка повинна чекати на заході на перехресті 2 до тих пір, поки вона не зможе в'їхати на хід 7, коли світлофор зелений, а потім досягне перехрестя 0 на хід 10, знову чекати на заході від перехрестя 1 до ходу 14, і нарешті в'їде на склад B в кінці ходу 17).