Big Maze

Time Limit : 8 sec, Memory Limit : 262144 KB

Big Maze

あなたは Jumbo Amusement Garden,略して「JAG」と呼ばれる巨大な遊園地で働いている.この遊園地の敷地は広大で,アトラクションもことごとく巨大なものが設置される.

この度JAGに,新たな巨大迷路アトラクション「Big Maze」が導入されることになった. Big Maze の形状は,平面図で見ると,縦横共に N マスの正方形状の迷路 M 個を,隣接する左右の辺同士を繋ぎ合わせ,縦 N マス,横 NM マスの長方形状になる予定である.

M 個の迷路を左からどの順番で繋ぎ合わせるかはあらかじめ決まっているが,隣り合う迷路のどの辺同士を繋ぎ合わせるかは未定である. M 個の迷路を繋ぎ合わせる前に,各迷路を90 度回転させる事が出来る.回転は何度でも行うことができ.回数は迷路毎に別々に決めてよい.回転させない迷路があってもかまわない.

各マスは通行可能な「通路」か,通行不可能な「壁」のいずれかであり,Big Maze の内部での移動は,上下左右の 4 方向に隣接する通路のマスに限り可能である.

Big Maze の左端の N 箇所に位置し,かつ通路であるマスをスタート地点とし,右端の N 箇所に位置し,かつ通路であるマスをゴール地点とする.

M 個の迷路を繋ぎ合わせる辺の選び方によっては,スタート地点やゴール地点が複数存在する場合や,存在しない場合もあり得る. また,スタート地点からゴール地点への経路が複数存在する場合や,存在しない場合もあり得る.

あなたの仕事は, 左から繋ぎ合わせる順番があらかじめ決まっている M 個の迷路を適切に回転させ,繋ぎ合わせる辺を上手く選ぶことで,スタート地点からゴール地点へ通路を移動して到達可能な縦 N マス,横 NM マスの長方形状の Big Maze を作ることが出来るか確認することである.

Input

入力は複数のデータセットからなり,各データセットが連続して与えられる. データセットの数は最大で 50 である. 各データセットは,次の形式で表される.

N M
maze1
maze2
...
mazeM

最初の行はふたつの整数 NM が空白区切りで与えられ,縦横 N マスの迷路が M 個与えられることを示し,1 ≤ N ≤ 12 かつ 1 ≤ M ≤ 1,000 である.

続いて,空白無しの N 文字を 1 行とする N 行の入力 mazeiM 回続く. ここで,1 ≤ i ≤ M である.

N 行の入力 mazei は,左から繋ぎ合わせる順番で数えたときの i 番目の迷路の情報を表し,以下の形式で与えられる.

c1, 1 c1, 2 ... c1, N
c2, 1 c2, 2 ... c2, N
...
cN, 1 cN, 2 ... cN, N

cj, k は,“.” または “#” のいずれか 1 文字で,上から j 番目かつ左から k 番目のマスの情報を表し,“.” のとき通路,“#”のとき壁である. ここで,1 ≤ j, k ≤ N である.

入力の終わりは,空白で区切られた 2 個のゼロからなる行で示される.

Output

各データセットについて,スタート地点からゴール地点へ移動可能な経路が少なくともひとつ存在する Big Maze を作ることが可能なら “Yes”,不可能なら “No” を 1 行で出力せよ.

Sample Input

3 2
#.#
...
#.#
###
...
###
3 2
#.#
...
#.#
###
#.#
###
3 3
#..
..#
###
..#
#.#
#..
#..
..#
###
5 3
.....
#####
##...
##.##
##...
.....
#####
.....
#####
.....
...##
##.##
...##
#####
.....
3 2
#.#
...
#.#
#.#
#.#
#.#
0 0

Output for Sample Input

Yes
No
Yes
Yes
Yes

以下に,サンプルデータセットの図を示す.












Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2017, 2017-07-02
http://acm-icpc.aitea.net/