Path Existence in a Grid

You are given an M × N grid, where each cell is either traversable or blocked. A traversable cell is represented by a dot ('.') and a blocked cell by a hash ('#'). Your task is to determine whether there exists a path from the top-left corner (cell at position (1,1)) to the bottom-right corner (cell at position (M,N)).

The player can move in the four cardinal directions: up, down, left, and right. The player cannot move outside the grid boundaries or into a blocked cell. Formally, if we denote the grid as \(G\) with dimensions \(M \times N\), then a valid move from \(G[i][j]\) is to \(G[i+dx][j+dy]\) where \((dx,dy) \in \{(-1,0), (1,0), (0,-1), (0,1)\}\) provided that \(0 \le i+dx < M\) and \(0 \le j+dy < N\), and \(G[i+dx][j+dy] = '.'\).

If the start cell or the destination cell is blocked, there is no valid path. Otherwise, determine whether a valid path exists and output YES or NO accordingly.

inputFormat

The first line contains two integers, M and N, representing the number of rows and columns in the grid respectively. This is followed by M lines, each containing a string of length N that represents a row of the grid.

Input is read from standard input.

outputFormat

Output a single line containing YES if there exists a path from the top-left corner to the bottom-right corner of the grid, otherwise output NO.

Output is written to standard output.

4 4
....
.##.
..#.
....

YES