006 - ICPCチョコレートの知的合同分割

双子の達也と和也はチョコレートが大好きである. かれらは大好物の板チョコレートを見つけたがそれはずいぶん変な形をしていた. ママの食べかけらしい. もちろん, 彼らはそれを食べる権利を主張し, 板チョコレートを切って二つのかけらにしてそれぞれの分け前とすることにした. チョコレートが公平に分割されたことを確信するために, 彼らは二つのかけらの形が「合同」であること, および, それぞれのかけらが「連結」していることを要求した.

板チョコレートはたくさんの正方形チョコレートでできており, それらは縁で隣接する正方形チョコレートと連結している. 板チョコレート全体も連結している.

この板チョコレートを正方形の縁に沿って切り, 二つの合同で連結なチョコレートのかけらに分割するのをあなたに手伝って欲しい. すなわち, 適切に回転, 裏返し, 移動することにより, 分割されたかけら同士がぴったり重なるようにするということである.

図 F-1: 18 個の正方形チョコレートからなる食べかけ板チョコレート

例として図 F-1 のような 18 個の正方形チョコレートからなる食べかけ板チョコレートを考える. これを正方形の縁に沿って切り, 図 F-2 のように, 9 個ずつの正方形からなる二つのかけらに分ける.

図 F-2: 板チョコレート (図 F-1) の分割

結果として, 二つの合同で連結なかけらが得られる. そのうちの一つは横縞模様の正方形 9 個からなり, もう一方は縦縞模様からなる. 上のかけらは, 時計回りに 90 度回転させて水平線を軸に裏返すと, 下のかけらにぴったり重なる.

図 F-3: 合同で連結な二つのかけらに分割できない図形

角でだけ接触している二つの正方形は連結していないとみなされる. 図 F-3 は合同で連結な二つのかけらに分割できない形の例である. 連結でなくてよければ, この形は 3 個の正方形からなる合同なかけらに 2 分割できることに 注意されたい (図 F-4).

図 F-4: 合同だが連結ではない二つのかけら

あなたの仕事は, 与えられた板チョコレートがこのような合同で連結な二つのかけらに分割できるかどうかを判定するプログラムを書くことである.

入力は，複数のデータセットからなり， 入力の終わりはスペースで区切られたゼロ二つからなる行である． 各データセットは，次の形式をしている．

w h
r(1, 1) ... r(1, w)
r(2, 1) ... r(2, w)
...
r(h, 1) ... r(h, w)

w と h は，それぞれ板チョコレートの幅と高さを示す整数であり, 2 ? w ? 10, 2 ? h ? 10 と仮定してよい． 続く h 行はそれぞれ，スペースで区切られた w 個の数字から構成されており， 数字 r(i, j) は， 場所 (i, j) の正方形チョコレートの有無を表す. その意味は，次の通り.

• '0': チョコレートなし (すでに食べられてしまった).
• '1': 正方形チョコレートあり.

最大で 36 個の正方形チョコレートがあること, すなわち, 各データセットにおける正方形チョコレートを表す '1' の個数は最大 36 であることを仮定してよい. また, 各行, 各列には少なくとも 1 個の正方形チョコレートがあることを仮定してよい.

板チョコレート全体は連結と仮定してよい． ママは板チョコレートに穴をあけるような食べ方はしないので, 図 F-5 のような穴のある形の板チョコレートを表すようなデータセットは無いことを仮定してよい.

図 F-5: 穴のある形の食べかけ板チョコレート (このようなデータセットは無いと仮定してよい)

出力は，入力データセットごとに "YES" または "NO" の大文字の文字列からなる. "YES" はそのデータセットが表す板チョコレートが 2 個の合同で連結なかけらに分割できることを意味し, "NO" はそのような分割が不可能なことを意味する. 出力行には他の文字があってはならない．

2 2
1 1
1 1
3 3
0 1 0
1 1 0
1 1 1
4 6
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 0
0 1 1 0
1 1 1 0
7 5
0 0 1 0 0 1 1
0 1 1 1 1 1 0
0 1 1 1 1 1 0
1 1 1 1 1 1 0
1 0 0 0 1 1 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
7 6
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
10 10
0 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
0 0

YES
NO
YES
YES
YES
NO
NO
YES