Problem Description

Input Format

$ N $ $ s_{(1,1)} $$ s_{(1,2)} $…$ s_{(1,N)} $ $ s_{(2,1)} $$ s_{(2,2)} $…$ s_{(2,N)} $ : $ s_{(N,1)} $$ s_{(N,2)} $…$ s_{(1,N)} $

• On the first line, you will be given an integer $ N $ ($2\ \leq\ N\ \leq\ 1,000$), the size of the grid.
• Following $ N $ lines show the color of each cell. Each line consists of . and #. The $ i $-th ($1\ \leq\ i\ \leq\ N$) row's $ j $-th ($1\ \leq\ j\ \leq\ N$) character represents the color of $(i,\ j)$. When the character is ., $(i,\ j)$ is painted white. When the character is #, $(i,\ j)$ is painted black.

Output Format

If you can reach $(N,\ N)$ no matter how Mr.X obstructs the way, output YES. If not, output NO. (Both without the period.)

Make sure to insert a line break at the end of the output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

YES

Sample Input #2

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

Sample Output #2

NO

Sample Input #3

2
.#
#.

Sample Output #3

NO

Notes/Hints

Problem

There is a two-dimensional grid of $N\ \times\ N$ cells. Let $(r,\ c)$ be the $ r $-th row's $ c $-th cell from the left. Some of these cells are painted black, other cells are painted white.

At first, you are at $(1,\ 1)$, and you want to go to $(N,\ N)$. However, there's a stranger Mr.X trying to obstruct your way to $(N,\ N)$.

You and Mr.X move in turns. At the beginning, Mr.X starts the move. On each move, each person can move as follows.

• Mr.X moves to one of the white cell adjoining to the cell where you are. If there is no cell Mr.X can move to, Mr.X disappears from the grid for that turn.
• You can move to one of the cells adjoining to the cell where you are, which Mr.X didn't move to in his last turn.

In other words, you can move to one of the adjoining cells. But before your move, Mr.X chooses one of the possible moves and blocks that. However, Mr.X can't block your move to a black cell.

You will be given the color of each cell. Determine if you can reach $(N,\ N)$ no matter how Mr.X obstructs your way.

Sample Explanation 1

If Mr.X blocks $(1,\ 2)$ at his first move, you can move to $(2,\ 1)$. After that, you can follow the black cells to reach $(4,\ 4)$. If Mr.X blocks $(2,\ 1)$, you can move to $(1,\ 2)$ and then follow the black cells to reach $(4,\ 4)$. Therefore, you can reach $(4,\ 4)$ notwithstanding Mr.X's obstruction. The answer is YES.

Sample Explanation 2

In this case, when you are at $(1,\ c)$, Mr.X can block $(2,\ c)$. If Mr.X follows this optimal strategy for him, you can't reach $(4,\ 4)$. The answer is NO.

Sample Explanation 3

In this case, Mr.X can block $ (2,2) $.

见题面 Input 部分

见题面 Output 部分