Problem:


MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

Falling Block Puzzle

ブロック落とし

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

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

 初期状態としていくつかのブロックが設置されている．

 2マス×2マス×2マスに収まるブロックの塊を上から落とす．ただし，落とす前に，ブロックがフィールドからはみ出さないようにして塊を水平方向に平行移動することができる．

 落としたブロックのうち，ある1つの下面が，すでに置かれているブロックまたはフィールドの底に着いた時点で，すべてのブロックの落下が止まり停止する．

 それぞれの段について，4マス全てが埋まっていればその段のブロックは消滅し，その上にあるブロックが1段ずつ落下する．落下後のそれぞれのブロックの下のセルにブロックがなかったとしても，それ以上落下することはない．

 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



Sample input:
1 1
##
#.
..
..
#.
..
1 1
.#
#.
#.
..
..
.#
2 2
##
#.
##
#.
..
.#
##
#.
#.
..
#.
..
1 3
#.
..
##
##
##
##
##
##
##
##
##
##
##
##
10 3
##
#.
##
#.
##
.#
##
.#
#.
##
#.
##
.#
##
.#
##
.#
#.
.#
#.
#.
.#
#.
.#
#.
..
#.
..
#.
..
#.
..
10 3
##
.#
##
..
##
#.
.#
..
##
.#
.#
##
.#
##
#.
##
##
.#
..
.#
#.
#.
.#
#.
#.
#.
#.
..
..
..
..
.#
0 0


Sample output:
1
0
3
6
6
0

Submission status: Wrong Answer

Solution code:
def block():
    return list(input() + input())


def get_drop():
    return [block(), block()]


def get_high():
    global high
    now = []
    for i in range(high):
        now.append(block())
    return now


def check(d, u):
    return d[0] == u[0] == "#" or d[1] == u[1] == "#"


def set_block(u, d):
    for i in range(4):
        if u[i] != ".": d[i] = u[i]


def puzzle0(d, u):
    for i in range(4):
        if d[i] == ".":
            d[i] = "#"
            return i


def puzzle1(d, u):
    global now
    if check(d[:2], u[:2]):
        if check(d[2:], u[2:]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle1_5(d, u):
    global now
    if check([d[0], d[2]], [u[0], u[2]]):
        if check([d[1], d[3]], [u[1], u[3]]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle2(d, u):
    global now
    for i in range(4):
        if d[i] == u[i] == "#":
            now.append(u)
            return True
    set_block(u, d)


def integrate(line):
    u1, u2 = line
    return ["#" if "#" in [u1[x], u2[x]] else "." for x in range(4)]


def jd(line, flg):
    global now
    if len(line) == 1:
        if flg: return 3
        return 2

    line = integrate(line)
    if line.count("#") == 1:
        return 0
    elif line == list("#..#") or line == list(".##.") or line.count("#") > 2:
        return 2
    elif line == list("##..") or line == list("..##"):
        return 1
    else: return 1.5


while True:
    high, drop = map(int, input().split())
    if high == drop == 0: break

    now = get_high()
    line = True
    count = 0
    for i in range(drop):
        line = get_drop()
        target = line[0]
        flg = True
        for j in range(2):
            target = line[j]
            if target.count("#") == 4:
                count += 1
                continue
            if not now:
                now.append(line)
                continue

            size = jd(line[:(2 - j)], flg)
            if size == 3:
                now.append(target)
            elif size == 0:
                to = puzzle0(now[-1], target)
                for x in range(4):
                    line[1][x] = "."
                line[1][to] = "#"
            elif size == 2:
                puzzle2(now[-1], target)
            elif 1:
                to = puzzle1(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]
            else:
                puzzle1_5(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]

            if now[-1].count("#") == 4:
                count += 1
                del now[-1]
                flg = False
    print(count)

Submission status: Wrong Answer

Solution code:
def block():
    return list(input() + input())


def get_drop():
    return [block(), block()]


def get_high():
    global high
    now = []
    for i in range(high):
        now.append(block())
    return now


def check(d, u):
    return d[0] == u[0] == "#" or d[1] == u[1] == "#"


def set_block(u, d):
    for i in range(4):
        if u[i] != ".": d[i] = u[i]


def puzzle0(d, u):
    for i in range(4):
        if d[i] == ".":
            d[i] = "#"
            return i


def puzzle1(d, u):
    global now
    if check(d[:2], u[:2]):
        if check(d[2:], u[2:]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle1_5(d, u):
    global now
    if check([d[0], d[2]], [u[0], u[2]]):
        if check([d[1], d[3]], [u[1], u[3]]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle2(d, u):
    global now
    for i in range(4):
        if d[i] == u[i] == "#":
            now.append(u)
            return True
    set_block(u, d)


def integrate(line):
    u1, u2 = line
    return ["#" if "#" in [u1[x], u2[x]] else "." for x in range(4)]


def jd(line, flg):
    global now
    if len(line) == 1:
        if flg: return 3
        return 2

    line = integrate(line)
    if line.count("#") == 1:
        return 0
    elif line == list("#..#") or line == list(".##.") or line.count("#") > 2:
        return 2
    elif line == list("##..") or line == list("..##"):
        return 1
    else: return 1.5


while True:
    high, drop = map(int, input().split())
    if high == drop == 0: break

    now = get_high()
    line = True
    count = 0
    for i in range(drop):
        line = get_drop()
        target = line[0]
        flg = True
        for j in range(2):
            target = line[j]
            if target.count("#") == 4:
                count += 1
                continue
            if not now:
                now.append(target)
                continue

            size = jd(line[:(2 - j)], flg)
            if size == 3:
                now.append(target)
            elif size == 0:
                to = puzzle0(now[-1], target)
                for x in range(4):
                    line[1][x] = "."
                line[1][to] = "#"
            elif size == 2:
                puzzle2(now[-1], target)
            elif 1:
                to = puzzle1(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]
            else:
                puzzle1_5(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]

            if now[-1].count("#") == 4:
                count += 1
                del now[-1]
                flg = False
    print(count)

Submission status: Wrong Answer

Solution code:
def block():
    return list(input() + input())


def get_drop():
    return [block(), block()]


def get_high():
    global high
    now = []
    for i in range(high):
        now.append(block())
    return now


def check(d, u):
    return d[0] == u[0] == "#" or d[1] == u[1] == "#"


def set_block(u, d):
    for i in range(4):
        if u[i] != ".": d[i] = u[i]


def puzzle0(d, u):
    for i in range(4):
        if d[i] == ".":
            if "#" in u: d[i] = "#"
            return i


def puzzle1(d, u):
    global now
    if check(d[:2], u[:2]):
        if check(d[2:], u[2:]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle1_5(d, u):
    global now
    if check([d[0], d[2]], [u[0], u[2]]):
        if check([d[1], d[3]], [u[1], u[3]]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle2(d, u):
    global now
    for i in range(4):
        if d[i] == u[i] == "#":
            now.append(u)
            return True
    set_block(u, d)


def integrate(line):
    u1, u2 = line
    return ["#" if "#" in [u1[x], u2[x]] else "." for x in range(4)]


def jd(line, flg):
    global now
    if len(line) == 1:
        if flg: return 3
        return 2

    line = integrate(line)
    if line.count("#") == 1:
        return 0
    elif line == list("#..#") or line == list(".##.") or line.count("#") > 2:
        return 2
    elif line == list("##..") or line == list("..##"):
        return 1
    else: return 1.5


while True:
    high, drop = map(int, input().split())
    if high == drop == 0: break

    now = get_high()
    line = True
    count = 0
    for i in range(drop):
        line = get_drop()
        flg = True
        for j in range(2):
            target = line[j]
            if target.count("#") == 4:
                count += 1
                continue
            if not now:
                now.append(target)
                continue

            size = jd(line[:(2 - j)], flg)
            if size == 3:
                now.append(target)
            elif size == 0:
                to = puzzle0(now[-1], target)
                for x in range(4):
                    line[1][x] = "."
                if "#" in line[1]: line[1][to] = "#"
            elif size == 2:
                puzzle2(now[-1], target)
            elif 1:
                to = puzzle1(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]
            else:
                puzzle1_5(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]

            if now[-1].count("#") == 4:
                count += 1
                del now[-1]
                flg = False
    print(count)

Submission status: Wrong Answer

Solution code:
def block():
    return list(input() + input())


def get_drop():
    return [block(), block()]


def get_high():
    global high
    now = []
    for i in range(high):
        now.append(block())
    return now


def check(d, u):
    return d[0] == u[0] == "#" or d[1] == u[1] == "#"


def set_block(u, d):
    for i in range(4):
        if u[i] != ".": d[i] = u[i]


def puzzle0(d, u):
    for i in range(4):
        if d[i] == ".":
            if "#" in u: d[i] = "#"
            return i


def puzzle1(d, u):
    global now
    if check(d[:2], u[:2]):
        if check(d[2:], u[2:]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle1_5(d, u):
    global now
    if check([d[0], d[2]], [u[0], u[2]]):
        if check([d[1], d[3]], [u[1], u[3]]):
            now.append(u)
        else:
            set_block(u, d)
            return 1
    else:
        set_block(u, d)
        return 0


def puzzle2(d, u):
    global now
    for i in range(4):
        if d[i] == u[i] == "#":
            now.append(u)
            return True
    set_block(u, d)


def integrate(line):
    u1, u2 = line
    return ["#" if "#" in [u1[x], u2[x]] else "." for x in range(4)]


def jd(line, flg):
    global now
    if len(line) == 1:
        if flg: return 3
        return 2

    line = integrate(line)
    if line.count("#") == 1:
        return 0
    elif line == list("#..#") or line == list(".##.") or line.count("#") > 2:
        return 2
    elif line == list("##..") or line == list("..##"):
        return 1
    else: return 1.5


while True:
    high, drop = map(int, input().split())
    if high == drop == 0: break

    now = get_high()
    line = True
    count = 0
    for i in range(drop):
        line = get_drop()
        flg = True
        for j in range(2):
            target = line[j]
            if target.count("#") == 4:
                count += 1
                continue
            if not now:
                now.append(target)
                continue

            size = jd(line[:(2 - j)], flg)
            if size == 3:
                now.append(target)
            elif size == 0:
                to = puzzle0(now[-1], target)
                if "#" in line[1]:
                    for x in range(4):
                        line[1][x] = "."
                    line[1][to] = "#"
            elif size == 2:
                puzzle2(now[-1], target)
            elif 1:
                to = puzzle1(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]
            else:
                puzzle1_5(now[-1], target)
                if to: line[1][:2], line[1][2:] = line[1][2:], line[1][:2]

            if now[-1].count("#") == 4:
                count += 1
                del now[-1]
                flg = False
            if target == list("...."): flg = False
    print(count)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    H, N = map(int, readline().split())
    if H == N == 0:
        return False
    def get_block():
        s = readline().strip()
        v = (s[0] == '#') + (s[1] == '#')*2
        s = readline().strip()
        v += (s[0] == '#')*4 + (s[1] == '#')*8
        return v
    R = []
    for i in range(H):
        R.append(get_block())
    R.extend([0]*8)
    H += 8
    I = []
    for i in range(N):
        v = get_block(); w = get_block()
        if v == 0:
            v, w = w, 0
        if v & 3 == 0 and w & 3 == 0:
            v >>= 2; w >>= 2
        if v & 5 == 0 and w & 5 == 0:
            v >>= 1; w >>= 1
        I.append((v, w))
    def dfs(i, R0):
        if i == N:
            return 0
        v0, w0 = I[i]
        r = 0
        for k, f in ((0, 0), (1, 5), (2, 3), (3, 0)):
            v = v0 << k; w = w0 << k
            if v >= 16 or w >= 16 or v & f or w & f:
                continue
            h = H-1
            while h and R0[h-1] & v == 0 and R0[h] & w == 0:
                h -= 1
            R = R0[:]
            R[h] |= v; R[h+1] |= w
            c = 0
            if R[h+1] == 15:
                for j in range(h+2, H):
                    R[j-1] = R[j]
                c += 1
            if R[h] == 15:
                for j in range(h+1, H):
                    R[j-1] = R[j]
                c += 1
            r = max(r, dfs(i+1, R) + c)
        return r
    write("%d\n" % dfs(0, R))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    e = LI()
    d = defaultdict(int)
    for i in e:
        d[i] += 1
    for i in d.values():
        if i != 2:
            print("no")
            break
    else:
        print("yes")
    return

#B
def B():
    n = I()
    a = LI()
    a.sort()
    ans = -float("inf")
    for c in range(n):
        for d in range(c):
            m = a[c]-a[d]
            for i in range(n)[::-1]:
                if i != c and i != d:
                    e = i
                    break
            for i in range(e)[::-1]:
                if i != c and i != d:
                    b = i
                    break
            ans = max(ans, (a[e]+a[b])/m)
    print(ans)
    return

#C
def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)

    s = input()
    n = len(s)
    if s.count("(") == 0:
        s = float(s)
        b = 10**(n-2)
        a = round(s*b)
        g = gcd(a,b)
        a //= g
        b //= g
    else:
        n = s.find("(")
        t = float(s[:n])
        b = 10**(n-2)
        a = round(t*b)
        g = gcd(a,b)
        a //= g
        b //= g
        l = (s.find("(")-s.find(".")-1)
        s = s[n+1:-1]
        m = len(s)
        c = round(float(s))
        d = (10**m-1)*10**l
        g = gcd(c,d)
        c //= g
        d //= g
        a = a*d+b*c
        b = b*d
        g = gcd(a,b)
        a //= g
        b //= g
    print(str(a)+"/"+str(b))
    return

#D
def D():
    return

#E
def E():
    def dfs(d,k,s):
        if d == n:
            ans.append(k)
        else:
            b = [block[d][i] for i in range(8)]
            if sum(b[:4]) == 0:
                b = b[4:]+[0,0,0,0]
            dfs(d+1,*check(b,k,s))
            if not (b[0]|b[1]|b[4]|b[5]):
                b_ = [b[2],b[3],0,0,b[6],b[7],0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[1]|b[3]|b[5]|b[7]):
                b_ = [0,b[0],0,b[2],0,b[4],0,b[6]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[2]|b[3]|b[6]|b[7]):
                b_ = [0,0,b[0],b[1],0,0,b[4],b[5]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[2]|b[4]|b[6]):
                b_ = [b[1],0,b[3],0,b[5],0,b[7],0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[1]|b[2]|b[3]|b[5]|b[6]|b[7]):
                b_ = [0,0,0,b[0],0,0,0,b[4]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[2]|b[3]|b[4]|b[6]|b[7]):
                b_ = [0,0,b[1],0,0,0,b[5],0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[1]|b[3]|b[4]|b[5]|b[7]):
                b_ = [0,b[2],0,b[6],0,0,0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[1]|b[2]|b[4]|b[5]|b[6]):
                b_ = [b[3],0,0,0,b[7],0,0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
    def check(b,k,s):
        i = 19
        k_ = k
        s_ = [[s[i][j] for j in range(4)] for i in range(20)]
        while i >= 1 and not ((b[0]&s[i-1][0])|(b[1]&s[i-1][1])|(b[2]&s[i-1][2])|(b[3]&s[i-1][3])|(b[4]&s[i][0])|(b[5]&s[i][1])|(b[6]&s[i][2])|(b[7]&s[i][3])):
            i -= 1
        s_[i] = [s_[i][j]+b[j] for j in range(4)]
        s_[i+1] = [s_[i+1][j]+b[j+4] for j in range(4)]
        i = 0
        while i < 20:
            if sum(s_[i]) == 4:
                k_ += 1
                for j in range(i,19):
                    s_[j] = [s_[j+1][l] for l in range(4)]
                s_[19] = [0,0,0,0]
                i -= 1
            i += 1
        return k_,s_

    while 1:
        h,n = LI()
        if h == n == 0:
            break
        s = [[0,0,0,0] for i in range(20)]
        for i in range(h):
            c = S()
            c += S()
            s[i] = [1 if c[j] == "#" else 0 for j in range(4)]
        block = [[0,0,0,0,0,0,0,0] for i in range(n)]
        for i in range(n):
            b = S()
            b += S()
            b += S()
            b += S()
            block[i] = [1 if b[j] == "#" else 0 for j in range(8)]
        ans = []
        dfs(0,0,s)
        print(max(ans))
    return

#F
def F():
    def dfs(d,k):
        if d == len(s):
            t.append(k)
        else:
            if s[d] == ".":
                for i in range(2):
                    dfs(d+1,k+[str(i)])
            else:
                dfs(d+1,k+[s[d]])

    def parse_expr(s,i):
        if f[s[i]]:
            n,i = parse_num(s,i)
            if i < len(s) and s[i] in "+-*":
                op,i = parse_op(s,i)
                e2,i = parse_expr(s,i)
                return calc(op,n,e2),i
            else:
                return n,i
        else:
            if s[i] == "(":
                i += 1
                e1,i = parse_expr(s,i)
                op,i = parse_op(s,i)
                e2,i = parse_expr(s,i)
                i += 1
            else:
                e1,i = parse_expr(s,i)
                op,i = parse_op(s,i)
                e2,i = parse_expr(s,i)
            return calc(op,e1,e2),i


    def parse_num(s,i):
        n = int(s[i])
        i += 1
        while i < len(s) and f[s[i]]:
            n *= 2
            n += int(s[i])
            i += 1
        return n,i

    def parse_op(s,i):
        return s[i],i+1

    def calc(op,e1,e2):
        if op == "+":
            return e1+e2
        elif op == "-":
            return e1-e2
        else:
            return e1*e2

    s = S()
    f = defaultdict(lambda : 0)
    for i in range(2):
        f[str(i)] += 1
    t = []
    dfs(0,[])
    for s in t:
        print(s)
        print(parse_expr(s,0))
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    E()