/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
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) は塗られていない。
高橋君はまだ塗られていないマスをそれぞれ白または黒で塗ることで、黒マス全体が長方形をなすようにしたいです。
より具体的には、ある 4 つの整数の組 (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 の文字列 - 黒く塗られたマスが 1 つ以上存在する。
入力
入力は以下の形式で標準入力から与えられる。
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
Score : 300 points
Problem Statement
You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:
- If the j-th character of S_i is
#, cell (i,j) is painted black. - If the j-th character of S_i is
., cell (i,j) is painted white. - If the j-th character of S_i is
?, cell (i,j) is not yet painted.
Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:
For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.
Determine whether this is possible.
Constraints
- 1 \leq H, W \leq 1000
- H and W are integers.
- Each S_i is a string of length W consisting of
#,.,?. - There is at least one cell that is already painted black.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
If it is possible to paint all the not-yet-painted cells so that the black cells form a rectangle, print Yes; otherwise, print No.
Sample Input 1
3 5 .#?#. .?#?. ?...?
Sample Output 1
Yes
The grid is in the following state. ? indicates a cell that are not yet painted.
By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:
Therefore, print Yes.
Sample Input 2
3 3 ?## #.# ##?
Sample Output 2
No
To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.
Sample Input 3
1 1 #
Sample Output 3
Yes