LeChuck’s Revenge#88
"I want to be a pirate!" is the famous catchphrase of Guybrush Threepwood from the Monkey Island game series. Guybrush embarks on a new adventure, and this time he desperately needs your help—it is a matter of life and death.
In his latest journey, Guybrush has sailed to the mysterious island TO, hoping to find clues about an even more mysterious treasure. However, LeChuck, upon learning about Guybrush's plans, sets up a trap for him there. The island is rectangular, and its map can be represented as a matrix of size R \times C. Each element of the matrix is called a cell (room). Some cells are impassable, filled with rocks and marked as R.
Refer to the illustration: this map is a 6 \times 7 matrix, where R indicates rocky (impassable) cells. Guybrush starts at the cell marked g, LeChuck starts at l, and Guybrush can escape the island by reaching the exit cell marked e.
In each unit of time, Guybrush may move to a horizontally or vertically adjacent cell (not diagonally), or stay in place, provided the destination cell is not rocky. Thus, each move can be up, down, left, right, or remain in the current cell. The same movement rules apply to LeChuck, except that LeChuck may not enter the exit cell e (he treats it as impassable). For example, on the given map, Guybrush's first move can be to stay in place or move left.
During each time unit, first Guybrush moves (or stays), then LeChuck moves (or stays). If after any turn Guybrush and LeChuck are in the same cell, LeChuck immediately catches Guybrush and wins.
Your task is to determine whether there exists at least one path from g to e for Guybrush, such that, regardless of how LeChuck moves, Guybrush will never be caught if he follows this path exactly. Such a path is called a safe path. For example, in the map above, the sequence "Left, Up, Up, Up, Right" (in moves) is a safe path, because LeChuck cannot catch Guybrush along this route in steps, regardless of his moves.
The first line contains (1 \leq T \leq 100) — the number of test cases.
For each test case: - The first line contains two integers and (4 \leq R, C \leq 30) — the number of rows and columns of the map. - The next lines each contain characters — the map. - The map contains exactly one g, one l, and one e. - Impassable rocky cells are R. - Passable empty cells are space characters ( ). - All cells on the boundary of the map are filled with rocks (R).
For each test case, print on a separate line: - YES if at least one safe path exists for Guybrush; - NO otherwise.
If a safe path exists, it is guaranteed that it can be traversed in no more than moves.
Example 2