C - Grid Repainting 2 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点:300300

問題文

HHWW 列のマス目で表されるキャンバスがあります. 上から ii 番目, 左から jj 番目のマスを (i,j)(i, j) と表します.
最初, すべてのマス目は白色です. square1001 君は, 黒い絵の具を使って絵を描きたいと思いました. 具体的には, square1001 君の目標は, si,j=s_{i, j}= # のときマス (i,j)(i, j) を黒色, si,j=s_{i, j}= . のときマス (i,j)(i, j) を白色にすることです.
しかし, 彼は絵を描くことが得意ではないので, 何回か (00 回でもよい)「上下左右に隣接する 22 つのマスを選び, 両方黒く塗る」ことしかできません. ただし, すでに黒く塗られているマスを選ぶこともでき, この場合マスの色は黒のまま変わりません.
square1001 君が目標を達成することができるか判定してください.

制約

  • HH11 以上 5050 以下の整数
  • WW11 以上 5050 以下の整数
  • すべての (i,j) (1iH,1jW)(i, j) \ (1 \leq i \leq H, 1 \leq j \leq W) に対して, si,js_{i, j}# または .

入力

入力は以下の形式で標準入力から与えられる.

HH WW
s1,1s1,2s1,3...s1,Ws_{1, 1} s_{1, 2} s_{1, 3} ... s_{1, W}
s2,1s2,2s2,3...s2,Ws_{2, 1} s_{2, 2} s_{2, 3} ... s_{2, W}
  ::   ::
sH,1sH,2sH,3...sH,Ws_{H, 1} s_{H, 2} s_{H, 3} ... s_{H, W}

出力

square1001 君が目標を達成することができるならば Yes、達成できないならば No と出力しなさい.


入力例 1Copy

Copy
3 3
.#.
###
.#.

出力例 1Copy

Copy
Yes

目標を達成する手順の一例として, 下の図の方法が挙げられます. この図では, 「次に黒く塗るマス」を「☆」で表しています.


入力例 2Copy

Copy
5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#

出力例 2Copy

Copy
No

square1001 君は目標を達成することができません.


入力例 3Copy

Copy
11 11
...#####...
.##.....##.
#..##.##..#
#..##.##..#
#.........#
#...###...#
.#########.
.#.#.#.#.#.
##.#.#.#.##
..##.#.##..
.##..#..##.

出力例 3Copy

Copy
Yes

Score: 300300 points

Problem Statement

We have a canvas divided into a grid with HH rows and WW columns. The square at the ii-th row from the top and the jj-th column from the left is represented as (i,j)(i, j).
Initially, all the squares are white. square1001 wants to draw a picture with black paint. His specific objective is to make Square (i,j)(i, j) black when si,j=s_{i, j}= #, and to make Square (i,j)(i, j) white when si,j=s_{i, j}= ..
However, since he is not a good painter, he can only choose two squares that are horizontally or vertically adjacent and paint those squares black, for some number of times (possibly zero). He may choose squares that are already painted black, in which case the color of those squares remain black.
Determine if square1001 can achieve his objective.

Constraints

  • HH is an integer between 11 and 5050 (inclusive).
  • WW is an integer between 11 and 5050 (inclusive).
  • For every (i,j)(i, j) (1iH,1jW)(1 \leq i \leq H, 1 \leq j \leq W), si,js_{i, j} is # or ..

Input

Input is given from Standard Input in the following format:

HH WW
s1,1s1,2s1,3...s1,Ws_{1, 1} s_{1, 2} s_{1, 3} ... s_{1, W}
s2,1s2,2s2,3...s2,Ws_{2, 1} s_{2, 2} s_{2, 3} ... s_{2, W}
  ::   ::
sH,1sH,2sH,3...sH,Ws_{H, 1} s_{H, 2} s_{H, 3} ... s_{H, W}

Output

If square1001 can achieve his objective, print Yes; if he cannot, print No.


Sample Input 1Copy

Copy
3 3
.#.
###
.#.

Sample Output 1Copy

Copy
Yes

One possible way to achieve the objective is shown in the figure below. Here, the squares being painted are marked by stars.


Sample Input 2Copy

Copy
5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#

Sample Output 2Copy

Copy
No

square1001 cannot achieve his objective here.


Sample Input 3Copy

Copy
11 11
...#####...
.##.....##.
#..##.##..#
#..##.##..#
#.........#
#...###...#
.#########.
.#.#.#.#.#.
##.#.#.#.##
..##.#.##..
.##..#..##.

Sample Output 3Copy

Copy
Yes


2025-04-21 (Mon)
09:15:12 +00:00