问题
有一个二维网格 N \times N 细胞。让 (r, c) 是 r-第行 c左侧第一个单元格。 其中一些单元被漆成黑色,其他单元被漆成白色。
首先你在 (1, 1),并且您想去 (N, N)。 然而,有一个陌生人 X 先生试图阻止你去 (N, N).
你和X先生轮流移动。一开始,X先生开始行动。 在每次移动时,每个人都可以按如下方式移动。
- X 先生搬到其中之一 白细胞 与您所在的牢房相邻。 如果没有 X 先生可以移动到的单元格,X 先生会在该回合从网格中消失。
- 您可以移动到与您所在单元格相邻的单元格之一,该单元格 Mr.X 在最后一个回合中没有移动到。
换句话说,您可以移动到相邻单元格之一。但在你采取行动之前,X 先生选择一种可能的行动并阻止它。然而,Mr.X 无法阻止你转移到黑色牢房。
您将获得每个单元格的颜色。确定您是否可以到达 (N, N) 无论X先生如何挡你的路。
输入
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)}
- 在第一行,您将得到一个整数 N (2 \leq N \leq 1,000),网格的大小。
- 正在关注 N 线显示每个单元格的颜色。每行由
.和#。 的 i-th (1 \leq i \leq N) 行的 j-th (1 \leq j \leq N) 字符代表颜色 (i, j)。 当角色是., (i, j) 被漆成白色。 当角色是#, (i, j) 被漆成黑色。
输出
如果你能到达 (N, N) 无论Mr.X如何挡路,输出 YES。
如果没有,则输出 NO。
(两者都没有句号。)
确保在输出末尾插入换行符。
输入示例 1
4 ..## ...# #..# ####
输出示例 1
YES
如果X先生阻止 (1, 2) 在他的第一步,你可以移动到 (2, 1)。之后你可以沿着黑色的格子到达 (4, 4).
如果X先生阻止 (2, 1) 您可以移至 (1, 2) 然后跟随黑色单元格到达 (4, 4).
因此,您可以达到 (4, 4) 尽管X先生阻挠。答案是 YES.
输入示例 2
4 ..## .... #..# ####
输出示例 2
NO
在这种情况下,当您位于 (1, c),X先生可以屏蔽 (2, c)。如果 Mr.X 遵循这个对他来说最优的策略,你就无法达到 (4, 4)。
答案是 NO.
输入示例3
2 .# #.
输出示例 3
NO
在这种情况下,X先生可以阻止 (2,2).