D. 网格涂色

    传统题 1000ms 256MiB

网格涂色

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个由 HHWW 列的格子组成的画布。我们用 (i,j)(i, j) 表示从上往下第 ii 行、从左往右第 jj 列的格子。 最初,所有格子都是白色的,小高 想用黑色颜料画画。

具体来说,小高 的目标是:当 si,j=#s_{i, j} = \texttt{\#} 时,将格子 (i,j)(i, j) 涂成黑色;当 si,j=.s_{i, j} = \texttt{.} 时,将格子 (i,j)(i, j) 保持为白色。

但是,他不擅长画画,只能进行若干次(可以为 00 次)“选择两个上下或左右相邻的格子,并将它们都涂成黑色”的操作。已经被涂成黑色的格子也可以再次被选择,这种情况下颜色不会发生变化。 请判断 小高 是否能够达成目标。

输入格式

输入通过标准输入给出,格式如下:

HH WW
s1,1s1,2s1,3s1,Ws_{1, 1} s_{1, 2} s_{1, 3} \ldots s_{1, W}
s2,1s2,2s2,3s2,Ws_{2, 1} s_{2, 2} s_{2, 3} \ldots s_{2, W}
\vdots
sH,1sH,2sH,3sH,Ws_{H, 1} s_{H, 2} s_{H, 3} \ldots s_{H, W}

输出格式

如果 小高 能够达成目标,输出 Yes;否则输出 No

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

说明/提示

限制条件

  • HH115050 之间的整数。
  • WW115050 之间的整数。
  • 对于所有 (i,j) (1iH, 1jW)(i, j)\ (1 \leq i \leq H,\ 1 \leq j \leq W)si,js_{i, j} 只会是 #.

样例解释 1

达成目标的一种操作顺序如下图所示。图中“☆”表示“下一步要涂黑的格子”。

样例解释 2

小高 无法达成目标。

图灵周赛 Round 24(二场)

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2025-9-6 18:00
结束于
2025-9-6 21:00
持续时间
3 小时
主持人
参赛人数
20