Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
971. Роботы
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 5G) |
| 11/07/2008 | Лето 2008 - 5 (G) |
| 28/10/2014 | Занятие 9 (C) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вы когда-нибудь видели роботов? Ну хотя бы одного? Нет? А вот мне довелось однажды… И не одного, а целых двух. Тогда я как раз умудрился попасть на транзисторный завод где-то под Хабаровском. Или Харбином… Теперь уже без разницы, но всё же. Так или иначе, я наблюдал за роботами. Два странных электромеханических парня неуклюже передвигались по территории склада, пытаясь за минимальное время достичь заданных оператором точек. Печальное зрелище… Сталкивающиеся лбами железяки и пунцовый оператор, пытающийся как-то разрешить ситуацию. Я тогда было подумал, что, быть может, есть возможность как-то улучшить… усовершенствовать этот процесс. Но застарелый интернетоголизм не дал раскрыться моему таланту. С завода меня вскоре уволили, и вот с тех пор я несколько охладел к работе… Но не к задаче! До сих пор, сидя в четыре утра на подоконнике в подъезде, я пытаюсь придумать, как же провести этих роботов сквозь все закоулки. Как бы это так завернуть…
Ввод
В первой строке – `N` (размер поля, `2\ ≤\ N\ ≤\ 30`). В следующих `N` строках – по `N` символов в каждой ('.' – пусто, 'x' – стена). Далее идут 2 строки, описывающие роботов в формате: `X_1,\ Y_1,\ X_2,\ Y_2` (`1\ ≤\ X_1,\ Y_1,\ X_2,\ Y_2\ ≤\ N`), где `X_1,\ Y_1` – номер столбца и строки, в которых находится робот в начале, `X_2,\ Y_2` – соответственно, куда он должен прийти. Начальные позиции роботов не совпадают.
Вывод
Минимальное количество шагов, за которое роботы могут прийти из своих начальных точек в конечные. На каждом шаге двигаться могут оба робота, но каждый из роботов может пойти только в незанятую другим роботом или стеной ячейку (в момент начала движения). Так же, два робота не могут пойти в одну и ту же ячейку одновременно. Естественно, на каждом шаге роботы могут ходить только в четыре соседние с ними ячейки: `(X-1,Y)`, `(X+1,Y)`, `(X,Y-1)`, `(X,Y+1)`. Так же роботы не могут выйти за края поля. Если роботы никогда не смогут занять свои конечные позиции, то вывести число `-1`.
Пример ввода
9 ......... ......... xxx...xxx ..xxxxx.. ......... ..xxxxx.. xxx...xxx ......... ......... 1 6 9 4 9 4 1 6
Пример вывода
18
