TSG LIVE! 14 プログラミングコンテスト
コンテスト日時
2025/05/25 (Su) 16:00 - 17:40

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.
提出
C++23 (g++ 12.2.0)