問題文
H行W列のマス目があります。このマス目の、上からi番目、左からj番目のマスを、マス(i,j)と呼ぶことにします。
各マスは黒または白で塗られています。
Si,jが#ならばマス(i,j)は黒色、. ならば白色です。
マス目の一番外側のマス、すなわち(1,j),(H,j),(i,1),(i,W)のいずれかの形で表されるマスは白であることが保証されます。
また、以下のことが保証されます。
- 黒いマスが少なくとも1つ存在する。
- 任意の黒い2マスは、辺を共有するマスへの移動を繰り返し、黒いマスのみを通って互いに到達可能である。
- 任意の黒い2マスは、辺を共有するマスへの移動を繰り返し、白いマスのみを通って互いに到達可能である。
黒いマスで構成される図形が「丸っぽい図形」であるかどうかを判定してください。
以下を満たすとき、黒いマスで構成される図形を丸っぽい図形であると定義します。
- 任意の黒い2マスについて、辺を共有するマスへの移動を繰り返すとき、最短経路が黒いマスのみで構成できる。
(最短経路は、通るマスが最も少ない経路です。)
制約
- 3≤H,W≤10
- Si,j は #または .
- S1,j,SH,j は .
- Si,1,Si,W は .
- #が少なくとも1つ存在する
入力
入力はすべて整数である。
H W
S1,1 S1,2 ... S1,W
S2,1 S2,2 ... S2,W
...
SH,1 SH,2 ... SH,W
出力
黒いマスで構成される図形が「丸っぽい図形」であるときは「Yes」
そうでないときは「No」を出力してください。
サンプル
入力1
4 4
....
.##.
.##.
....
この図形は丸っぽい図形といえます。
入力2
5 5
.....
.###.
..#..
.###.
.....
(2,2)から(2,4)への最短経路は(2,2)→(2,3)→(2,4)のみですが、
(2,3)は白いマスのため、この図形は丸っぽい図形ではありません。
入力3
5 5
.....
.#...
.##..
..##.
.....