[プログラマーレベル2][1]友人4枚Python

📝問題の説明

ブラインド公債を通じた新入社員のライアンが新しいゲームの開発を担当する.今回発売されるゲーム名はfriends 4ブロックです
同じ形状のカメラレンズブロック2×これは2つの形で4つ貼ってあると、消えていくにつれて点数が得られるゲームです.

プレートが上に示されている場合、ライアンは2を得ることができます.×2ブロック×7、コンソール×2×2で配置された4つのブロックはクリアされます.同じブロックに複数の2を含む×2に含めることができ、消去条件を満たす2×2複数の形があれば、一気に消すことができます.

ブロックがクリアされると、上のブロックが下に落ち、空白を埋めます.

空白のスペースを埋めたら、再び2×2つの同じ形の塊が集まると、再び消され、繰り返し落下します.

上の初期レイアウトは以下のように文字で表されています.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
各文字は、ライアン(R)、ムージ(M)、アピチ(A)、フロド(F)、ニオ(N)、トゥゲン(T)、ジェシー(J)、コン(C)を表す.
指定されたブロックの最初の配置を入力すると、削除されたブロックが全部で何個あるかを判断するプログラムを作成します.

入力フォーマット

進入板の高さm,幅n,板の配置情報板を入力する.
2 ≦ n, m ≦ 30
boardは、m個の長さnの文字列の配列で与えられる.ブロックを表す文字は、大文字AにZを使用します.

出力フォーマット

指定したレイアウト情報を入力し、消去するブロックを出力します.

I/O例

mnboardanswer45[CCBDE, AAADE, AAABF, CCBBF]1466[TTTANT, RRFACC, RRRFCC, TRRRAA, TTMMMF, TMMTTJ]15

🚩ソリューション

を使用して、指定された2番目のマザーボードのリストを列と行で置き換えます.

bfsで展開し、現在位置+DELTA=[(0,0),(1,0),(0,1),(1,1)]をそれぞれチェックし、すべてのブロックが同じブロックであれば2 x 2正方形を削除するブロックとすることができる.

行で、削除するブロックを0に変更し、行ごとに0のNull=対応する数*["x"]を作成します.

の空のリストを左側に入力し、削除されていないブロックまたは削除されたブロックのリストの後ろに「x」として貼り付けます.
(左から塗りつぶすのは、最初にリストの列と行が変更されたためで、左から塗りつぶすのではありません)

✔問題を解く

def bfs(m, n, board):
    x, y=0, 0
    DELTA=[(0, 0), (1, 0), (0, 1), (1, 1)]
    del_info=set()
    # bfs search
    while True:
        for i in range(4):
            dy, dx = DELTA[i]
            if board[y][x]!=board[y+dy][x+dx] or board[y][x]=='x':
                break
        else:
            del_info.add((y, x))
            del_info.add((y+1, x))
            del_info.add((y, x+1))
            del_info.add((y+1, x+1))

        if x+1 == m-1 and y+1 != n-1:
            x=0
            y+=1
        elif x+1 < m-1:
            x+=1
        elif y+1 == n-1:
            break

    # board_set
    for y, x in del_info:
        board[y][x]=0
    # board_update
    for i, row in enumerate(board):
        empty=['x']*row.count(0)
        board[i]=empty+[block for block in row if block!=0]

    return len(del_info)

def solution(m, n, board):
    cnt = 0
    b=list(map(list,zip(*board)))

    while True:
        # bfs로 정사각형 4개 모양의 블록 찾기
        del_cnt=bfs(m, n, b)
        if del_cnt==0: # 더 이상 삭제 시킬 것이 없음
            return cnt
        cnt+=del_cnt