Начало
ЗадачиПодразделы
Другие разделы
| STL |
| Антагонистические игры |
| Геометрия |
| Графы |
| Динамическое программирование |
| Дихотомия |
| Длинная арифметика |
| Комбинаторика |
| Неклассифицированные |
| Основы |
| Перебор |
| Поиск в глубину |
| Последовательности |
| Сортировка |
| Теория чисел |
Дата и время
17/11/2024 09:18:26
Поиск в ширину
Lines
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 5E) |
| 12/07/2006 | Лето 2006 - 5 (E) |
| 22/11/2008 | Занятие 9 (C) |
| 09/12/2010 | Сборы: Общий итог (4A) |
| 17/12/2010 | Занятие 12 (A) |
| 30/12/2010 | Сборы 4: Практика (A) |
| 26/11/2013 | Занятие 10 для начинающих (A) |
| 03/07/2019 | Лето 2019 - 2 (B) |
| 14/12/2022 | Курс I - BFS (проводит BOGAT) (A) |
| 05/07/2023 | Лето 2023-5 простые (C) |
| 11/12/2023 | Графы: BFS (проводит BOGAT) (A) |
| 03/07/2024 | Лето 2024-5 простые (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В таблице из `N` строк и `N` столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.
Ввод
В первой строке находится число `N` (`2\ ≤\ N\ ≤\ 250`), в следующих `N` строках – по `N` символов. Символом точки обозначена свободная клетка, латинской заглавной O – шарик, @ – исходное положение шарика, который должен двигаться, латинской заглавной X – конечное положение шарика.
Вывод
В первой строке выводится "Y", если движение возможно, или "N", если нет. Если движение возможно, далее следует `N` строк по `N` символов – как и на вводе, но буква X, а также все точки по пути заменяются плюсами.
Пример ввода 1
5 ....X .OOOO ..... OOOO. @....
Пример вывода 1
Y +++++ +OOOO +++++ OOOO+ @++++
Пример ввода 2
5 ..X.. ..... OOOOO ..... ..@..
Пример вывода 2
N
Пример ввода 3
5 ...X. ..... O.OOO ..... ....@
Пример вывода 3
Y ..++. .++.. O+OOO .++++ ....@
