← 返回题目列表

AtCoder · abc422_b

D. 环形绳

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

分数: 200 点

问题陈述

有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i第行 (1\le i\le H) 从顶部和 j第列 (1\le j\le W) 从左边开始。

每个单元格都涂有一种颜色,白色或黑色。 细胞上绘制的颜色表示为 H 字符串 S _ 1,S _ 2,\ldots,S _ H。当 j- 第一个字符 (1\le j\le W) of S _ i\ (1\le i\le H) is .,细胞 (i,j) 被漆成白色,并且当 j- 第一个字符 (1\le j\le W) of S _ i\ (1\le i\le H) is #,细胞 (i,j) 被漆成黑色。

判断网格是否满足以下条件:

  • 对于每个黑色单元格,被涂成黑色的水平或垂直相邻单元格的数量为 2 or 4.

这里,细胞 (i,j)\ (1\le i\le H,1\le j\le W) 和 (k,l)\ (1\le k\le H,1\le l\le W) 水平或垂直相邻当且仅当 |i-k|+|j-l|=1.

约束

  • 1\le H\le 20
  • 1\le W\le 20
  • H 和 W 是整数。
  • S _ i 是一个长度为的字符串 W 组成 . 和 # (1\le i\le H).

输入

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

H W
S _ 1
S _ 2
\vdots
S _ H

输出

输出 Yes 如果给定的网格满足条件,并且 No 如果不满足条件。


样本输入 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

示例输出 1

Yes

例如,细胞 (6,3) 被涂成黑色,并且在相邻单元格之间 (5,3),(6,2),(6,4),(7,3),细胞 (5,3) 和 (6,4) 被漆成黑色,即 2 细胞,因此满足条件。

每个其他黑色单元格也满足条件,因此输出 Yes.


示例输入 2

1 2
##

示例输出 2

No

细胞 (1,1) 被涂成黑色,但它只有一个相邻单元格,因此不满足条件。

因此,输出 No.


示例输入 3

4 3
...
...
...
...

示例输出 3

Yes

没有黑色单元格,因此满足条件。

因此,输出 Yes.


示例输入 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

示例输出 4

Yes