Falling Block Puzzle

時間制限 : 8 sec, メモリ制限 : 262144 KB

Falling Block Puzzle

ブロック落とし

あなたはある落ち物パズルで遊んでいる. このパズルのフィールドは,下図のように各段に立方体のセルが2マス×2マスに並び,段が上に無限に並んでいる形をしている.

それぞれのセルは,セルにぴったり収まるブロックが1つ存在するか,何もないかのどちらかである. このパズルは以下のように進行する.

  1. 初期状態としていくつかのブロックが設置されている.
  2. 2マス×2マス×2マスに収まるブロックの塊を上から落とす.ただし,落とす前に,ブロックがフィールドからはみ出さないようにして塊を水平方向に平行移動することができる.
  3. 落としたブロックのうち,ある1つの下面が,すでに置かれているブロックまたはフィールドの底に着いた時点で,すべてのブロックの落下が止まり停止する.
  4. それぞれの段について,4マス全てが埋まっていればその段のブロックは消滅し,その上にあるブロックが1段ずつ落下する.落下後のそれぞれのブロックの下のセルにブロックがなかったとしても,それ以上落下することはない.
  5. 2に戻る.

初期状態で置かれているブロックと,落とす塊がいくつか与えられるので,与えられる順に全ての塊を落とすことで,最大いくつの段を消すことができるかを求めるプログラムを作れ.

Input

入力は100個以下のデータセットからなる.各データセットは以下の形をしている.

(初期状態のブロックの高さ H ) (落とす塊の数 N )
(初期状態の1段目)
...
(初期状態の H 段目)
(1個目の落とす塊)
...
( N 個目の落とす塊)

各データセットの1行目には初期状態のブロックの高さ H (1 ≤ H ≤ 10)と落とす塊の数 N (1 ≤ N ≤ 3)が指定されている. 続いて初期状態のそれぞれ段の情報が以下の形式で与えられる.

c11 c12
c21 c22

cijはそれぞれのセルの情報を表し,'#'はブロックが存在することを,'.'はブロックがないことを表す.1段目から H 段目までのそれぞれの段について,全てのセルにブロックが存在したり,全てのセルにブロックがなかったりすることはないと仮定して良い. 続いてそれぞれの落とす塊の情報が以下の形式で与えられる.

b111 b112
b121 b122
b211 b212
b221 b222

初期状態の形式と同様に'#'はブロックが存在することを,'.'はブロックがないことを表す.それぞれの塊には少なくとも1つのブロックが含まれる.塊に含まれるブロックは角や辺のみで接していることがあり,面で繋がっているとは限らない.

初期状態・ブロックの塊の入力の添え字の対応は以下の図を参照すること.

入力の終わりは,2つのゼロからなる1行で示される.

なお,下図は,後に示す Sample Input 中の最初のデータセットを表している.このデータセットでは,ブロックの塊を斜めに平行移動した後に落下させることで1つの段を消すことができる.

Output

各データセットに対して,最大でいくつの段を消すことができるかを1行に出力せよ.

Sample Input

1 1
##
#.
..
..
#.
..
1 1
.#
#.
#.
..
..
.#
2 2
##
#.
##
#.
..
.#
##
#.
#.
..
#.
..
1 3
#.
..
##
##
##
##
##
##
##
##
##
##
##
##
10 3
##
#.
##
#.
##
.#
##
.#
#.
##
#.
##
.#
##
.#
##
.#
#.
.#
#.
#.
.#
#.
.#
#.
..
#.
..
#.
..
#.
..
10 3
##
.#
##
..
##
#.
.#
..
##
.#
.#
##
.#
##
#.
##
##
.#
..
.#
#.
#.
.#
#.
#.
#.
#.
..
..
..
..
.#
0 0

Output for Sample Input

1
0
3
6
6
0

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2015, 2015-06-14
http://acm-icpc.aitea.net/