No.179 塗り分け

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 154
作問者 : ぴろずぴろず

25 ProblemId : 454 / 出題時の順位表

問題文

縦$H$,横$W$のマスからなる長方形があります。各マスは白または黒で塗られています。
yuki君は黒のマス全てを赤か青に塗り替えることにしました。また、赤青それぞれ少なくとも1マスは塗り、赤で塗られたマスと青で塗られたマスが平行移動して一致するようにしたいと思っています。
yuki君の望む塗りかたが可能なら"YES"、不可能なら"NO"を出力してください。(""は不要です)

注:同じマスに複数の色を塗ることはできません。yuki君は白のマスは塗り替えません。

入力

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

一行目に$H$,$W$がスペース区切りで与えられます。
続く$H$行には、マスの$i$行目の塗られかたを表す長さ$W$の文字列$S_i$が与えられます。
$S_i$の$j$文字目が"#"の時、$i$行$j$列のマスは黒で塗られていることを表し、"."の時、白で塗られていることを表します。(""は含まれません)

$1 \leq H \leq 50$
$1 \leq W \leq 50$
$S_i$は"#"と"."のみから構成される文字列である。(""は含まれません)

出力

"YES"または"NO"を出力してください。(""は不要です)
最後に改行してください。

サンプル

サンプル1
入力
3 3
##.
###
.#.
出力
YES

次のように塗り分けられるので、"YES"を出力します。

サンプル2
入力
5 3
.#.
.#.
.#.
.#.
.#.
出力
NO

どのような塗り分けをしても一致しません。したがって、"NO"を出力します。

サンプル3
入力
3 9
######...
#.####.#.
######...
出力
YES

次のように塗り分けられるので、"YES"を出力します。

元のマスの塗られ方には穴や、離れている部分があることがあります。
また、塗り分け方にも穴や離れている部分があっても構いません。

サンプル4
入力
3 5
#...#
##.##
#...#
出力
NO

塗り分けたマスは平行移動のみで一致しなければならないことに注意してください。
回転や反転はできません。

サンプル5
入力
5 8
###.....
#.####..
..####..
..####.#
.....###
出力
YES

サンプル6
入力
23 33
...............##................
...........##########............
.......##################........
...##########################....
.##....##################....##..
.######....##########....######..
.##########....##....##########..
.##....########..##############..
.######....####..##############..
.##############..##############..
.##############..##############..
.##############..##############..
...############..############....
.......########..########........
...........####..####............
...............##................
.................................
........#...#...........#........
........#...............#........
#.#.#.#.#.#.#.###.###.###.###.#.#
#.#.#.#.##..#.#...#.#.#.#.##..##.
.#..###.#.#.#.###.###.###.###.#..
#................................
出力
NO

提出ページヘ