Условие:
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