Задача M. Лабиринт

Автор:Общеизвестная   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно. В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх, вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.

Формат входного файла

Первая строка входного файла содержит числа N и M - количества строк и столбцов в описании лабиринта соответственно. В следующих N строках содержатся по M символов из множества '.' (пустое пространство) , '#' (стена), 'S' (вход), 'F' (выход). В описании лабиринта присутствует ровно один символ 'S' и ровно один 'F'.

Формат выходного файла

Выведите в выходной файл текстовую строку 'YES', если существует путь от входа к выходу и 'NO' в противном случае.

Ограничения

1 ≤ N,M ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
S#.
.#F
...
YES
2
3 3
S#.
.#F
#..
NO

0.099s 0.015s 15