| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 5 | 5 | 100.000% |
Одним погожим деньком на плацу проходили учения. Если точнее, то шла отработка тактически важных строевых приемов: команд <<направо>>, <<налево>>, <<кругом>> и <<шаг вперед>>. Стояла пятиградусная жара, и солдаты скучали, в отличии от работника спецслужб потенциального врага, прибывшего на плац с целью оценки боевой готовности войск.
Разведчика звали Смит, и трудился он в поте лица, делая снимки настолько часто, что буквально через три часа у него закончилась пленка. Проклиная себя за безалаберность, он покинул место проведения учений и вернулся лишь через 28ドル$ минут 12ドル$ секунд, захватив на этот раз с собой все снаряжение.
Внимательно изучив обстановку, Смит понял, что за прошедшее время лишь один солдат сменил свое месторасположение. Поскольку ему не хочется признаваться в провале, он решил провернуть пару интриг и списать в конечном счете нехватку снимков на пожар в одной из африканских деревень. Смит --- парень изворотливый, и такого рода вещи для него не составляют труда. Единственное, что осталось узнать --- двигались ли за время его отсутствия другие солдаты, ведь они могли просто вернуться на свое место в ходе сложного тактического маневра. Кроме того, начальство может спросить, сколько команд было отдано в тот интервал времени, что не отражен на пленке.
Теперь перед Смитом стоит задача: узнать, за какое минимальное число команд солдат мог переместиться из одной позиции в другую. Для наглядности, представим плац прямоугольным полем размера $N \cdot M,ドル а солдата на нем --- фигурой, занимающей три подряд идущие смежные клетки. Далее проиллюстрировано выполнение команд.
Команда <<налево>> ...... ...... ...... ...\.. ..\-/. ...|.. ...... .../.. ...... ......
Команда <<направо>> ...... ...... ...... .../.. ..\-/. ...|.. ...... ...\.. ...... ......
Команда <<кругом>> ....... ....... ...\-/. .../-\. ....... ....... ....... .......
Команда <<шаг вперед>> ....... ...\-/. ...\-/. ....... ....... ....... ....... .......
Вам, как человеку проверенному, поручено войти в доверие к Смиту, решив для него эту задачу.
В первой строке входного файла содержатся два целых числа $N$ и $M$ (1ドル \le N, M \le 100$). Далее следуют $N$ строк по $M$ символов каждая --- описание исходного положения солдата на плаце. Формат описания аналогичен примерам выше. Символом <<*>> задаются препятствия --- клетки, занимать которые солдат в процессе своего перемещения не может --- так Смит обозначил других солдат и противопехотные мины.
Далее в аналогичном формате следует описание конечное положение солдата. Гарантируется, что все препятствия остались на своих местах.
В выходной файл выведите минимальное количество команд, которое необходимо отдать солдату, чтобы он переместился из начального положения в конечное. Если же такое перемещение невозможно, выведите в выходной файл число <<$-1$>>.
4 7 ....... ....... .../-\. ....... ...\-/. ....... ....... .......
3
4 7 ....... ******* .../-\. ....... ...\-/. ******* ....... .......
-1