[白俊21609][python]サメ中学校

質問する
サメ中学校のコードサークルはゲームを組織した.このゲームのサイズはNです×nのメッシュでは、初期メッシュの各セルに黒いブロック、虹のブロック、および普通のブロックが含まれるブロックが含まれます.一般ブロックにはM色があり、色はM以下の自然数で表される.黒いブロックは-1、虹のブロックは0を表します.(i,j)は、グリッドのi番行、j番列、|r 1-r 2|+|c 1-c 2|=1は、満たす2つのセル(r 1,c 1)と(r 2,c 2)が隣接するセルを表す.
ブロックグループは、接続ブロックの集合です.グループには少なくとも1つの普通のブロックがあり、普通のブロックの色はすべて同じでなければなりません.虹のブロックがいくらあっても、黒いブロックを含めることはできません.グループに属するブロックの数は2以上でなければなりません.任意のブロックからグループに属する隣接するセルに移動し、グループに属する他のすべてのセルに移動できます.ブロック群の基準ブロックは虹のブロックではなく、行番号が最も小さいブロックであり、このようなブロックが複数ある場合、列番号が最も小さいブロックである.
今日はこのゲームに自動再生機能を作ります.自動再生は、ブロックグループが存在するときに次の手順を繰り返します.
最大サイズのブロック群

を探します.このようなブロック群が複数ある場合、虹のブロックの数が最も多いブロック群が含まれ、そのようなブロックが複数ある場合、基準ブロックの行が最大、すなわち複数である場合、列の最大のブロックが検索される.

1で見つかったブロックグループのすべてのブロックを削除します.ブロック群に含まれるブロック数をBと呼ぶと、B 2点が得られる.

重力は

メッシュに作用する.

ラスタは反時計回りに90度回転します.

重力がメッシュに再び作用します.重力が

メッシュに作用すると、黒いブロックを除くすべてのブロックが行番号の大きいセルに移動します.他のブロックやメッシュの境界に遭遇するまで移動します.

入力
最初の行は、メッシュエッジのサイズN、色の個数Mを与える.
2行目からN行目まで、グリッドセル内のブロックの情報が1行目からN行目まで順次与えられます.各ローの情報は、1番目のカラムからNカラムの順に表示されます.入力欄の情報は,−1,0,M以下の自然数のみからなる.
しゅつりょく
最初の行で取得したスコアの和を出力
解決策
関数find()を記述して、最大サイズのブロック群

を検索する.ここで最大のブロック群は複数であり,虹のブロックの数が同じ場合,コードを細かく計算して記述する(この部分の誤りが最も多い).私の場合、比較オブジェクトの値は毎回格納され、最大のブロックグループが変化するとすぐに更新されます.

重力作用の関数を記述します.

90度反時計回りに回転する関数を記述します.

コード#コード#

from collections import deque
# 게임은 크기가 N×N인 격자에서 진행
n, m = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 

# 1. 크기가 가장 큰 블록 그룹을 찾는다. 
def find(board):
    # 여러 블록 그룹 중 가장 큰 블록 그룹의 크기
    max_size = 0
    # 가장 큰 블록 그룹의 번호
    max_group = -1
    # 가장 큰 블록 그룹이 가지고 있는 무지개 블록의 수
    max_rainbow = 0
    # 블록 그룹의 번호
    count = 0
    # bfs를 위한 큐
    queue = deque([])
    # 각 그룹 블록에 포함되는 좌표 저장
    his = {} 
    #레인보우 블록의 좌표 저장
    rainbow_loc = {}
    #일반 블록의 좌표 저장
    block_loc = {}
    # 방문 배열 초기화
    visit = [list(0 for _ in range(n)) for _ in range(n)]

    for i in range(n):
        for j in range(n):
            # 블록 그룹의 크기
            size = 1
            # 블록 그룹에 포함된 레인보우 블록
            rainbow = 0
            
            # 일반 블록이라면
            if 0 < board[i][j] <= m and visit[i][j] == 0: 
                visit[i][j] = 1
                count += 1
                queue.append([i, j])
                color = board[i][j] # 시작하는 일반 블록의 색상 저장
                his[count] = [[i, j]]
                block_loc[count] = [[i, j]]
                rainbow_loc[count] = []

                while queue:
                    #print(queue)
                    r, c = queue.popleft()
                    #visit[r][c] = 1
                    # print("start", color, r, c, count)
                    
                    for k in range(4):
                        nx = r + dx[k]
                        ny = c + dy[k]

                        if 0<=nx<n and 0<=ny<n and (board[nx][ny]==color or board[nx][ny]==0) and visit[nx][ny] == 0:
                            #print(color, nx, ny, count, board[nx][ny])
                            if board[nx][ny] == 0:
                                # print("chk")
                                rainbow += 1
                                rainbow_loc[count].append([nx, ny])
                            else:
                                block_loc[count].append([nx, ny])
                            his[count].append([nx, ny])
                            queue.append([nx, ny])
                            visit[nx][ny] = 1
                            size += 1
                
                for x, y in rainbow_loc[count]:
                    visit[x][y] = 0

                # print("count", count)
                # for v in visit:
                #     print(v)
                # print("")
            
                block_loc[count].sort()
            #print(max_size, size)
                if max_size < size:
                    max_size = size
                    max_group = count
                    max_rainbow = rainbow
                # 1.1. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
                elif max_size == size:
                    if max_rainbow < rainbow:
                        max_size = size
                        max_group = count
                        max_rainbow = rainbow
                    # 1.2. 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 
                    elif max_rainbow == rainbow:
                        # print(max_group, block_loc[max_group], count, block_loc[count])
                        if block_loc[max_group][0][0] < block_loc[count][0][0]:
                            max_size = size
                            max_group = count
                            max_rainbow = rainbow
                        # 1.3. 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
                        elif block_loc[max_group][0][0] == block_loc[count][0][0]:
                            if block_loc[max_group][0][1] < block_loc[count][0][1]:   
                                max_size = size
                                max_group = count
                                max_rainbow = rainbow
                #print(max_group)
            
    #max_group이 -1이라면 블록 그룹이 없으므로 게임을 종료한다
    # 2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B**2점을 획득한다.
    if max_group < 1 or max_size < 2:
        return -1, board
    
    for i in range(n):
        for j in range(n):
            if [i, j] in his[max_group]:
                board[i][j] = 6 # 사라진 곳은 6으로 표시
    return max_size**2, board

# 3. 격자에 중력이 작용한다.
# 중력 작용 함수 6 - 빈칸
def move(board):
    for i in range(n):
        for j in range(n-1, -1, -1):
            #print(i, j)
            if board[j][i] != 6 and board[j][i] != -1:
                start = j
                #print("s", start)
                while 0<=start+1<n and board[start+1][i] == 6:
                    #print(start)
                    board[start+1][i] = board[start][i]
                    board[start][i] = 6
                    start += 1

    return board

# 4. 격자가 90도 반시계 방향으로 회전한다.
def rotate(board):
    result = []
    for i in range(n-1, -1, -1):
        temp = []
        for j in range(0, n):
            temp.append(board[j][i])
        result.append(temp)
    return result

# 5. 다시 격자에 중력이 작용한다.

# 격자에 중력이 작용하면 "검은색 블록을 제외한 모든 블록"이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
# for b in board:
#     print(b)
# print("")

ans = 0
while True:
    s, b = find(board)

    # print("그룹 확인 후 삭제")
    # for bb in b:
    #     print(bb)
    # print("", ans)

    if s == -1:
        break

    ans += s

    m_b = move(b)
    r_b = rotate(m_b)
    m_b = move(r_b)
    board = m_b

    # for mm in m_b:
    #     print(mm)
    # print("")

print(ans)