Grid Path :
Difficulty Level : Medium
Submissions : 241
Asked In :
Marks :10
: 1 | : 0
Given a grid with N rows and M columns, consisting of the following symbols:
- '#' represents obstacle
- '.' represents path
- 'S' represents starting point
- 'E' represents ending point
You cannot travel through obstacles, and consider only the cells sharing an edge to be adjacent. (4 - adjacency)
Please tell if there exists a path from 'S' to 'E' following the above conditions.
Input
First line contains 2 space separated integers N (1 <= N <= 1e5) and M (1 <= M <= 1e5), N*M <= 1e6.
Next N lines contains string of M length consisting of characters '#', '.', 'S' and 'E'.
There exists exactly one 'S' and 'E' in the grid.
Output
Output "YES" if the path exists, "NO" if the path doesn't exist.
Examples
Input
5 5 #..#. S#..# ....# #.#E# #####
Output
YES
Input
5 5 #..#. S#..# ...## #.#E# #####
Output
NO
