SZ#G4M03. 【GESP强化 四级】黑色邻格

提交1 通过1
通过率100%
时间限制1000ms
内存限制256MiB
    ID: 11190 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 普及- 上传者: 标签>GESPGESP强化C++c++编程题二维数组二维字符数组四邻域检查

题目描述

小泽要用黑色颜料在一块 H×WH\times W 的白色方格板上画出给定图案。一次操作可以选择两个上下或左右相邻的方格,把这两个方格都涂成黑色。已经是黑色的方格也可以再次被选择,再次涂色后仍然是黑色。目标图案用 # 表示黑格、. 表示白格。

判断是否存在一种操作方法,能够恰好画出给定图案。换句话说,需要判断能否通过若干次上述操作,使最终黑色方格的位置与给定图案完全一致。

输入格式

第一行输入两个整数 HHWW,分别表示方格板的行数和列数。

接下来 HH 行,每行输入一个长度为 WW、只包含字符 #. 的字符串,表示最终要画出的图案。

输出格式

如果能够画出给定图案,输出 Yes;否则输出 No

3 3
.#.
###
.#.
Yes
5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
No
11 11
...#####...
.##.....##.
#..##.##..#
#..##.##..#
#.........#
#...###...#
.#########.
.#.#.#.#.#.
##.#.#.#.##
..##.#.##..
.##..#..##.
Yes

样例解释

  • 样例 1 的每个黑格都至少与另一个黑格共边,可以通过若干次相邻双格涂色得到。
  • 样例 2 中存在孤立黑格,它不能被任何一次合法操作单独涂黑,因此输出 No
  • 样例 3 中虽然图案分成若干部分,但每个黑格仍有共边的黑格,因此可以完成。

数据范围与约定

  • 1H,W501 \le H,W \le 50