← 返回题目列表

AtCoder · code_festival_china_i

I. 障碍

中文机器翻译题面 查看原题

问题

有一个二维网格 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).