Path Finding in a Grid

You are given an n x m grid, where each cell is either open ('.') or blocked ('#'). Your task is to determine if there exists a path from the top-left cell (i.e., cell at row 0, column 0) to the bottom-right cell (i.e., cell at row n-1, column m-1) moving only in the four cardinal directions (up, down, left, right).

Note: The path must only pass through open cells ('.'). Additionally, if either the starting cell or the ending cell is blocked, the answer is NO.

The problem can be formally stated in LaTeX as:

Given an $n \times m$ grid $G$, where each element $G_{ij}$ is either \(\texttt{.}\) (open) or \(\texttt{#}\) (blocked), determine whether there exists a path from \(G_{0,0}\) to \(G_{n-1,m-1}\) such that every visited cell is open and movements are allowed only to adjacent cells in four directions.

inputFormat

The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000) indicating the number of rows and columns of the grid, respectively. The following n lines each contain a string of length m composed of characters '.' and '#' representing the grid.

Example:

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

outputFormat

Output YES if there exists a valid path from the top-left to the bottom-right cell, otherwise output NO.

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

YES