H. Лабиринт ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт Ваня играет в игру, в которой нужно вывести шарик из лабиринта. Лабиринт представляет собой прямоугольную доску размера n×m , каждая клетка которой либо пустая,

1 октября 2025
Программирование

Условие:

H. Лабиринт
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Ваня играет в игру, в которой нужно вывести шарик из лабиринта. Лабиринт представляет собой прямоугольную доску размера n×m
, каждая клетка которой либо пустая, либо занята препятствием. Изначально в одной из пустых клеток находится шарик.

За одно действие Ваня может выбрать одно из четырех направлений: вверх, вниз, влево или вправо, и шарик начнет двигаться в этом направлении, пока не упрется в клетку с препятствием или пока не выкатится за границы доски. Обратите внимание, что в процессе движения шарик остановить нельзя.

Помогите Ване узнать по заданному лабиринту и начальному положению шарика, можно ли такими движениями выкатить шарик за пределы лабиринта.

Входные данные
В первой строке через пробел даны два числа n
, m
— размеры лабиринта (1≤n,m≤50
).

В последующих n
строках дано по m
символов:

«#» обозначает клетку с препятствием;
«.» обозначает пустую клетку;
«x» обозначает начальное положение шарика.
Гарантируется, что x
встречается ровно один раз.

Выходные данные
Выведите «Yes», если возможно выкатить шарик из лабиринта, и «No» в противном случае.

Примеры
Входные данныеСкопировать
5 7
####.##
#.#...#
#x#...#
#...#.#
##.##.#
Выходные данныеСкопировать
Yes
Входные данныеСкопировать
5 5
#####
#x..#
#...#
#...#
##.##
Выходные данныеСкопировать
No
Входные данныеСкопировать
5 5
#####
#...#
#.x.#
#...#
##.##
Выходные данныеСкопировать
Yes

Решение:

Для решения задачи о лабиринте, в котором нужно выяснить, может ли шарик выкатиться за пределы доски, мы можем использовать простой алгоритм. Мы будем двигать шарик в каждом из четырех направлений (вверх, вниз, влево, вправо) до тех пор, пока он не столкнется с препятствием или не выйдет за границы доски. Если шарик выходит за границы, мы выводим Yes, в противном случае - No.

Вот пример реализации на Python:

1. : Эта функция принимает размеры лабиринта, сам лабиринт и начальные координаты шарика. Она проверяет, может ли шарик выкатиться за пределы лабиринта, двигаясь в каждом из четырех направлений. 2. : Внутри цикла мы продолжаем двигать шарик в выбранном направлении, пока он не столкнется с препятствием или не выйдет за границы. 3. : Мы считываем размеры лабиринта и сам лабиринт, а затем находим начальную позицию шарика. 4. : В зависимости от результата проверки выводим Yes или No. Этот код должен корректно решать задачу в заданных ограничениях.