F - Land Division 2
Darjeeling
3
s
1024
MB
400
点
問題文
TSG 国は南北方向に距離 $H$、東西方向に距離 $W$ の長方形の形をしており、 $H$ 行 $W$ 列のマス目状に領域が区切られています。北から $i$ 番目、西から $j$ 番目の領域を $(i, j)$ と呼ぶことにします。
マス目の状態は $H$ 個の長さ $W$ の文字列 $S_1, \ldots S_H$ で表され、 $S_i$ の $j$ 文字目が #
のとき $(i,j)$ は陸地、 .
のとき$(i,j)$ は海を表します。
このたび TSG 国は Rho 国と Tau 国に分離することとなりました。争いを避けるため、以下の条件を満たすように陸地を分割したいです。
- TSG 国の陸地であった領域はすべて Rho 国か Tau 国のどちらかに属する。
- Rho 国に属する陸地と Tau 国に属する陸地は平行移動によってぴったり重なり合う。
このような分割が可能かどうか判定してください。
制約
- $H, W$ は整数
- $1\leq H,W \leq 100$
- $S_i$ は
#
、.
からなる長さ $W$ の文字列 - TSG 国は少なくとも1つの陸地を持つ
入力
入力は以下の形式で標準入力から与えられる。
$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$
出力
条件を満たす分割が可能ならば Yes
を、不可能ならば No
を出力せよ。
入力例 1
3 2
##
##
##
出力例 1
Yes
例えば、以下のように分割すれば良いです。
RT
RT
RT
入力例 2
3 3
#..
#.#
###
出力例 2
No
条件を満たす分割は存在しません。
入力例 3
3 3
.##
###
.#.
出力例 3
Yes
例えば、以下のように分割すれば良いです。
.RR
TTR
.T.