← 返回题目列表

AtCoder · abc390_c

E. 绘制一个矩形

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

分数: 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