Maze Pathfinding: Is There a Valid Path?

Given a maze represented by an n × m grid, determine if there exists a path from the top-left corner to the bottom-right corner. The grid consists only of '.' (denoting open space) and '#' (denoting an obstacle). A valid move can be made in four directions: up, down, left, and right.

The problem can be mathematically formulated as follows:

If we let \( G \) be an \( n \times m \) matrix where \( G_{ij} \) is either \( '.' \) or \( '#' \), determine whether there exists a sequence of coordinates \( (x_0,y_0), (x_1,y_1), \dots, (x_k,y_k) \) such that:

• \( (x_0,y_0) = (0,0) \) and \( (x_k,y_k) = (n-1, m-1) \),
• \( G_{x_i,y_i} = '.' \) for all \( 0 \leq i \leq k \),
• For every \( i \), \( |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1 \) (i.e., moves are only allowed in one of the four cardinal directions).

Output "YES" if such a path exists, and "NO" otherwise.

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the maze respectively. The following \( n \) lines each contain a string of length \( m \) representing the maze.

Example:

3 3
... 
##.
...

outputFormat

Output a single line containing the answer "YES" if there exists a path from the top-left to the bottom-right, and "NO" if no such path exists.

## sample

3 3
...
##.
...

YES