Grid Pathfinding

You are given an n x m grid consisting of characters. Each cell in the grid is either open, represented by a dot ., or blocked, represented by a hash #. Your task is to determine whether it is possible to travel from the top-left corner of the grid (cell (0, 0)) to the bottom-right corner (cell (n-1, m-1)) without stepping on a blocked cell.

You may move in four directions: up, down, left, and right. Formally, you need to check whether there exists a sequence of cells $$ (x_0, y_0), (x_1, y_1), \ldots, (x_k, y_k) $$ such that:

• $$ (x_0, y_0) = (0, 0) $$ and $$ (x_k, y_k) = (n-1, m-1); $$
• For every consecutive pair, the Manhattan distance is 1;
• All cells in the path contain . (i.e. they are open).

If such a path exists, print YES; otherwise, print NO.

inputFormat

The input begins with a line containing two integers, n and m (1 ≤ n, m ≤ 1000), representing the number of rows and columns respectively. Each of the following n lines contains a string of length m consisting solely of the characters . and #.

outputFormat

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

3 3
..#
#..
##.

YES