/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 H マス、横 W マスのマス目があります。 上から i 行目 (1\le i\le H) 、左から j 列目 (1\le j\le W) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは白もしくは黒のどちらか 1 色で塗られています。
マスに塗られている色は H 個の文字列 S _ 1,S _ 2,\ldots,S _ H で表され、S _ i\ (1\le i\le H) の j 文字目 (1\le j\le W) が . のとき、マス (i,j) は白で塗られており、S _ i\ (1\le i\le H) の j 文字目 (1\le j\le W) が # のとき、マス (i,j) は黒で塗られています。
マス目が以下の条件を満たすか判定してください。
- どの黒で塗られたマスについても、上下左右で隣り合うマスのうち黒く塗られているものは 2 つもしくは 4 つである。
ただし、マス (i,j)\ (1\le i\le H,1\le j\le W) とマス (k,l)\ (1\le k\le H,1\le l\le W) は、|i-k|+|j-l|=1 であるとき、かつそのときに限り上下左右で隣り合っているとします。
制約
- 1\le H\le 20
- 1\le W\le 20
- H,W は整数
- S _ i は
.および#からなる長さ W の文字列 (1\le i\le H)
入力
入力は以下の形式で標準入力から与えられる。
H W S _ 1 S _ 2 \vdots S _ H
出力
与えられたマス目が条件を満たしているとき Yes を、条件を満たしていないとき No を出力せよ。
入力例 1
8 7 .###### ##....# #.###.# #.#.#.# #.#.#.# #.##### #...#.. #####..
出力例 1
Yes
例えば、マス (6,3) は黒で塗られており、隣り合っているマス (5,3),(6,2),(6,4),(7,3) のうち、マス (5,3) およびマス (6,4) の 2 マスが黒で塗られているため、条件を満たしています。
他の黒で塗られたどのマスについても条件を満たしているため、Yes を出力してください。
入力例 2
1 2 ##
出力例 2
No
マス (1,1) は黒で塗られていますが、隣り合っているマスは 1 つしかないため、条件を満たしていません。
よって、No を出力して下さい。
入力例 3
4 3 ... ... ... ...
出力例 3
Yes
黒で塗られているマスがないため、条件を満たしています。
よって、Yes を出力してください。
入力例 4
15 18 ##.###..##.##..##. ##.#.##.##.##.#### ...##.#.......#### ###.###....###.##. #.##.......#.#.... #..#.##.##.#.#.... #.########.####.## #.##.##.#....##.## #......##......... ##.##..#..##..#### .#.#####..#####..# .#..#...##.#.....# .#..#.####.#.....# .##.#.#.#..##..### ..###.###...####..
出力例 4
Yes
Score : 200 points
Problem Statement
There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and the j-th column (1\le j\le W) from the left.
Each cell is painted with one color, white or black.
The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.
Determine whether the grid satisfies the following condition:
- For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.
Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.
Constraints
- 1\le H\le 20
- 1\le W\le 20
- H and W are integers.
- S _ i is a string of length W consisting of
.and#(1\le i\le H).
Input
The input is given from Standard Input in the following format:
H W S _ 1 S _ 2 \vdots S _ H
Output
Output Yes if the given grid satisfies the condition, and No if it does not satisfy the condition.
Sample Input 1
8 7 .###### ##....# #.###.# #.#.#.# #.#.#.# #.##### #...#.. #####..
Sample Output 1
Yes
For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.
Every other black cell also satisfies the condition, so output Yes.
Sample Input 2
1 2 ##
Sample Output 2
No
Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.
Therefore, output No.
Sample Input 3
4 3 ... ... ... ...
Sample Output 3
Yes
There are no black cells, so the condition is satisfied.
Therefore, output Yes.
Sample Input 4
15 18 ##.###..##.##..##. ##.#.##.##.##.#### ...##.#.......#### ###.###....###.##. #.##.......#.#.... #..#.##.##.#.#.... #.########.####.## #.##.##.#....##.## #......##......... ##.##..#..##..#### .#.#####..#####..# .#..#...##.#.....# .#..#.####.#.....# .##.#.#.#..##..### ..###.###...####..
Sample Output 4
Yes