AT_abc390_c [ABC390C] Paint to make a rectangle
题目描述
给定一个 $H$ 行 $W$ 列的网格。
以下将从上往下第 $i$ 行 $(1 \leq i \leq H)$、从左往右第 $j$ 列 $(1 \leq j \leq W)$ 的格子称为格子 $(i, j)$。
网格的状态由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示如下：
- 若 $S_i$ 的第 $j$ 个字符是 `#`，则格子 $(i, j)$ 被涂黑。
- 若 $S_i$ 的第 $j$ 个字符是 `.`，则格子 $(i, j)$ 被涂白。
- 若 $S_i$ 的第 $j$ 个字符是 `?`，则格子 $(i, j)$ 未被涂色。
高桥君希望通过将未被涂色的格子分别涂白或涂黑，使得所有黑色格子形成一个矩形。
更具体地说，需要存在四个整数 $(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$，则格子 $(i, j)$ 被涂黑。
> - 否则，格子 $(i, j)$ 被涂白。
请判断是否存在这样的涂色方案。
输入格式
输入从标准输入给出，格式如下：
> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
若可以通过涂色使得所有黑色格子形成矩形，则输出 `Yes`；否则输出 `No`。
说明/提示
### 约束条件
- $1 \leq H, W \leq 1000$
- $H$ 和 $W$ 为整数
- $S_i$ 是由 `#`、`.`、`?` 组成的长度为 $W$ 的字符串
- 至少存在一个被涂黑的格子
### 样例解释 1
网格的初始状态如下（`?` 表示未涂色的格子）：
将格子 $(1, 3)$、$(2, 2)$、$(2, 4)$ 涂黑，并将格子 $(3, 1)$、$(3, 5)$ 涂白后，所有黑色格子可形成如下矩形：
因此输出 `Yes`。
### 样例解释 2
若要使所有黑色格子形成矩形，必须将格子 $(2, 2)$ 涂黑，但该格子已被涂白。因此无法满足条件，输出 `No`。
翻译由 DeepSeek R1 完成