← 返回题目列表

AtCoder · abc096_c

C. 网格重画2

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

分数: 300 点

问题陈述

我们有一个画布,分为一个网格,其中 H 行和 W 列。广场位于 i从顶部开始的第行和 j从左边算起的第列表示为 (i, j).
最初,所有方块都是白色的。 square1001想要用黑色颜料画一幅画。他的具体目标是让 Square (i, j) 黑时 s_{i, j}= #,并制作 Square (i, j) 白时 s_{i, j}= ..
然而,由于他不是一个好的画家,他只能选择两个水平或垂直相邻的方块,并将这些方块涂成黑色,一定次数(可能为零)。他可能会选择已经涂成黑色的方块,在这种情况下,这些方块的颜色仍然是黑色。
确定 square1001 是否可以实现他的目标。

约束

  • H 是介于 1 和 50 (含)。
  • W 是介于 1 和 50 (含)。
  • 对于每个 (i, j) (1 \leq i \leq H, 1 \leq j \leq W), s_{i, j} is # or ..

输入

输入由标准输入按以下格式给出:

H W
s_{1, 1} s_{1, 2} s_{1, 3} ... s_{1, W}
s_{2, 1} s_{2, 2} s_{2, 3} ... s_{2, W}
  :   :
s_{H, 1} s_{H, 2} s_{H, 3} ... s_{H, W}

输出

如果 square1001 能够实现他的目标,则打印 Yes;如果他不能,请打印 No.


示例输入 1

3 3
.#.
###
.#.

示例输出 1

Yes

下图显示了实现该目标的一种可能方法。在这里,正在绘制的方块用星星标记。


示例输入 2

5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#

示例输出 2

No

square1001在这里无法实现他的目标。


示例输入 3

11 11
...#####...
.##.....##.
#..##.##..#
#..##.##..#
#.........#
#...###...#
.#########.
.#.#.#.#.#.
##.#.#.#.##
..##.#.##..
.##..#..##.

示例输出 3

Yes