Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB
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 following.
In other words, you can move to one of the adjoining cell. But before your move Mr.X choose one of the possible move and block 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.
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)}
.
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.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.
4 ..## ...# #..# ####
YES
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
.
4 ..## .... #..# ####
NO
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
.
2 .# #.
NO
In this case, Mr.X can block (2,2).