Problem C
Dragons in a Dungeon
Grog has found himself lost in a dungeon, and must find his way out, which is conveniently marked with a red EXIT sign. Before he starts, he would like to know if it is even possible to get out of this dungeon, as it is filled with many scary monsters. As much as Grog loves a scuffle, he would prefer to avoid them at all costs. In each square of the dungeon, there one of four possibilities:
-
G - Grog; this is the square in which Grog begins his journey.
-
. - An empty cell; Grog can move freely through one of these cells.
-
M - A scary monster; Grog won’t move through one of these cells.
-
E - The exit.
Your job is to tell Grog if there is a way out of the dungeon by moving through only empty squares. Since D&D is non-euclidean, Grog can move into any of the eight adjacent squares.
Input
There are multiple lines of input to this program. The first line is composed of $2$ space-separated integers: $r$ $c$. $r$ is the number of rows in the dungeon ($2 \leq r \leq 40$). $c$ is the number of columns in the dungeon ($2 \leq c \leq 40$). The next $r$ lines are strings of $c$ characters ($G$, $.$, $M$, $E$) corresponding to the four possibilities of each cell.
Output
Output ’YES’ if there is a path for Grog to get out of the dungeon or ’NO’ if there is not.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 GME .M. ..M |
YES |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 4 .MM. GM.E .MM. |
NO |
