Path Existence in a Grid

Charlie is in a grid where each cell is either passable ('.') or blocked ('#'). Starting from the top-left cell (0, 0), Charlie wants to reach the bottom-right cell (M-1, N-1) by moving only in the four cardinal directions (up, down, left, right) without stepping into any blocked cell. Determine whether there exists such a path.

More formally, given a grid (G) of dimensions (M \times N) defined by: [ G_{ij} = \begin{cases} '.' & \text{if cell } (i, j) \text{ is free},\ '#' & \text{if cell } (i, j) \text{ has an obstacle}, \end{cases} ] you need to decide if there exists a path from cell ( (0,0) ) to cell ( (M-1,N-1) ) such that all visited cells are free. Output (\texttt{YES}) if a path exists and (\texttt{NO}) otherwise.

inputFormat

The first line of input contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (M) and (N) separated by a space, indicating the number of rows and columns in the grid. The next (M) lines each contain a string of length (N) representing the grid where a dot ('.') denotes a free cell and a hash ('#') denotes an obstacle. The input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing either (\texttt{YES}) if there exists a valid path from the start to the destination or (\texttt{NO}) if such a path does not exist. The output should be printed to standard output (stdout).## sample

2
3 3
..#
.#.
...
4 4
....
..#.
.#..
....

YES
YES