[BOJ]2058-魔法使いサメと吹雪

質問リンク
20058-魔法使いサメと火狐嵐
問題の説明
2^N*2^Nサイズのメッシュにサメが炎の嵐を放つ.
A[r][C]は(r,c)上の氷の量を表す.A[r][c]がゼロであれば、氷がないことを示す.
火狐嵐の過程は以下の通りである.

段階L結晶

2^L × 2^Lサイズの部分メッシュ

すべてのローカルメッシュを90度

回転

氷の3つの格子または隣接しない格子があり、氷量は1つの

減少する.
Qのように火炎嵐を繰り返し,メッシュ上に残った氷の総量と最大のブロックが占める格子数を求めた.
問題を解く
氷の減少部分やbfsで氷量、塊の大きさを求める部分は比較的容易である.コアはメッシュの回転90度を区切る部分で、
メッシュを分割して90度回転
各クエリーについて、グリッドを分割して90度回転する部分は次のとおりです.
問題では,所与の流れに従ってメッシュ分割→分割メッシュzipを用いて90度回転→プレートに再投入し,周期順に実現する.

def rotate_90(parts):
    return list(zip(*parts[::-1]))

# 1. 2^L * 2^L로 나누기
    for i in range(0, 2**N, 2**L):
        for j in range(0, 2**N, 2**L):
            parts = []
            for k in range(i, i+2**L):
                parts.append(board[k][j:j+2**L])
            # 2. 90도 회전
            rotated = rotate_90(parts)
            for k in range(2**L):
                board[k+i][j:j+2**L] = rotated[k]

回転の感覚があるので、グーグルは他のコードを使って、公式を求めて直接回転するよりもzipを直接使うほうが直感的なので、別途修正していません.
氷の量を減らす
隣接する格子では,氷のある格子が3個未満の場合,直ちに板を更新するのではなく,減少した氷の量を新しいリストに記録すべきであることに注目すべきである.

# 3.얼음의 양 줄이기
    decrement = [[0 for _ in range(2**N)] for _ in range(2**N)]
    for i in range(2**N):
        for j in range(2**N):
            if board[i][j] > 0:
                count = 0
                for d in range(4):
                    ni, nj = i+dx[d], j+dy[d]
                    if in_bound(ni, nj):
                        if board[ni][nj] > 0:
                            count += 1
                if count < 3:
                    decrement[i][j] = -1
    for i in range(2**N):
        for j in range(2**N):
            board[i][j] += decrement[i][j]

総氷量と氷の大きさを得る

def bfs(x, y, visited):
    queue = deque()
    queue.append([x,y])
    visited[x][y] = True
    count = 1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx,ny) and not visited[nx][ny] and board[nx][ny] > 0:
                visited[nx][ny] = True
                queue.append([nx, ny])
                count += 1
    return count

answer1 = 0
for i in range(2**N):
    answer1 += sum(board[i])
    
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
answer2 = 0
for i in range(2**N):
    for j in range(2**N):
        if not visited[i][j] and board[i][j] > 0:
            answer2 = max(answer2, bfs(i,j,visited))

完全なコード

import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, Q = map(int, input().split())
board = []
for _ in range(2**N):
    board.append(list(map(int, input().split())))
Levels = list(map(int, input().split()))

def rotate_90(parts):
    return list(zip(*parts[::-1]))

def in_bound(x, y):
    if x in range(2**N) and y in range(2**N):
        return True
    return False

def bfs(x, y, visited):
    queue = deque()
    queue.append([x,y])
    visited[x][y] = True
    count = 1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx,ny) and not visited[nx][ny] and board[nx][ny] > 0:
                visited[nx][ny] = True
                queue.append([nx, ny])
                count += 1
    return count

for L in Levels:
    # 1. 2^L * 2^L로 나누기
    for i in range(0, 2**N, 2**L):
        for j in range(0, 2**N, 2**L):
            parts = []
            for k in range(i, i+2**L):
                parts.append(board[k][j:j+2**L])
            # 2. 90도 회전
            rotated = rotate_90(parts)
            for k in range(2**L):
                board[k+i][j:j+2**L] = rotated[k]
    
    # 3.얼음의 양 줄이기
    decrement = [[0 for _ in range(2**N)] for _ in range(2**N)]
    for i in range(2**N):
        for j in range(2**N):
            if board[i][j] > 0:
                count = 0
                for d in range(4):
                    ni, nj = i+dx[d], j+dy[d]
                    if in_bound(ni, nj):
                        if board[ni][nj] > 0:
                            count += 1
                if count < 3:
                    decrement[i][j] = -1
    for i in range(2**N):
        for j in range(2**N):
            board[i][j] += decrement[i][j]
                      
# 남은 얼음합
answer1 = 0
for i in range(2**N):
    answer1 += sum(board[i])
    
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
answer2 = 0
for i in range(2**N):
    for j in range(2**N):
        if not visited[i][j] and board[i][j] > 0:
            answer2 = max(answer2, bfs(i,j,visited))

print(answer1)
print(answer2)

所要時間
2時間半
青少年サメより難しいようです