分数: 300 点
问题陈述
给你一个网格 H 行和 W 列。
让 (i,j) 表示行中的单元格 i (1 \leq i \leq H) 从顶部和列 j (1 \leq j \leq W)从左边开始。
网格的状态表示为 H 字符串 S_1, S_2, \ldots, S_H,每个长度 W,如下:
- 如果 j- 第一个字符 S_i is
#,细胞 (i,j) 被漆成黑色。 - 如果 j- 第一个字符 S_i is
.,细胞 (i,j) 被漆成白色。 - 如果 j- 第一个字符 S_i is
?,细胞 (i,j) 尚未绘制。
Takahashi 想要将每个尚未绘制的单元格涂成白色或黑色,以便所有黑色单元格形成一个矩形。
更准确地说,他希望存在整数的四元组 (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W)使得:
对于每个单元格 (i,j) (1 \leq i \leq H, 1 \leq j \leq W), 如果 a \leq i \leq b 和 c \leq j \leq d,单元格为黑色;
否则,单元格为白色。
确定这是否可行。
约束
- 1 \leq H, W \leq 1000
- H 和 W 是整数。
- 每个 S_i 是一个长度为 W 组成
#,.,?. - 至少有一个单元已被涂成黑色。
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
如果可以绘制所有尚未绘制的单元格,使黑色单元格形成一个矩形,请打印 Yes;否则,打印 No.
示例输入 1
3 5 .#?#. .?#?. ?...?
示例输出 1
Yes
网格处于以下状态。 ? 表示尚未绘制的单元格。

通过绘制单元格 (1,3), (2,2),和 (2,4) 黑色和细胞 (3,1) 和 (3,5) 白色,黑色单元格可以形成一个矩形,如下所示:

因此,打印 Yes.
示例输入 2
3 3 ?## #.# ##?
示例输出 2
No
要形成一个包含所有黑色单元格的矩形,您需要绘制单元格 (2,2) 黑色,但已经被漆成白色。
因此,不可能让所有黑色单元格形成一个矩形,所以打印 No.
示例输入 3
1 1 #
示例输出 3
Yes