백준/python 20058 마법사 상어와 파이어스톰

# @Date : 2024-10-07 17:31:26
# @Author : ecodev
# @Link : http://ecodev-blog.vercel.app

import sys
from collections import deque
input = sys.stdin.readline

############ ---- Input Functions ---- ############


def inp():
    return(int(input()))


def inlt():
    return(list(map(int, input().split())))


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


def invr():
    return(map(int, input().split()))


n, q = invr()
graph = [inlt() for _ in range(2 ** n)]
magic = inlt()

# 배열 돌리기


def rotate(graph, l):
    new_graph = [[0] * 2 ** n for _ in range(2 ** n)]

    for i in range(0, 2 ** n, 2 ** l):
        for j in range(0, 2 ** n, 2 ** l):
            for x in range(2 ** l):
                for y in range(2 ** l):
                    new_graph[i + y][j + (2 ** l - 1 - x)
                                     ] = graph[i + x][j + y]

    return new_graph


path = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def melt(graph):
    now = []
    for x in range(2 ** n):
        for y in range(2 ** n):
            cnt = 0
            if graph[x][y] > 0:
                for i in range(4):
                    nx = x + path[i][0]
                    ny = y + path[i][1]

                    if 0 <= nx < 2 ** n and 0 <= ny < 2 ** n and graph[nx][ny] > 0:
                        cnt += 1

                # 동시성 조심
                if cnt < 3:
                    now.append((x, y))

    for x, y in now:
        graph[x][y] -= 1


def BFS(x, y):
    global ice
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    ice += 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + path[i][0]
            ny = y + path[i][1]

            if 0 <= nx < 2 ** n and 0 <= ny < 2 ** n and not visited[nx][ny] and graph[nx][ny] > 0:
                ice += 1
                visited[nx][ny] = True
                q.append((nx, ny))


for i in range(q):
    graph = rotate(graph, magic[i])
    melt(graph)


ans = 0
visited = [[False] * (2 ** n) for _ in range(2 ** n)] 
# 제곱할 때 곱하기와 혼동하여 연산순서가 바뀔 수 있기 때문에 반드시 괄호를 쓰자.
for i in range(2 ** n):
    for j in range(2 ** n):
        if graph[i][j] > 0 and not visited[i][j]:
            ice = 0 # 할 때마다 ice를 새로 비교해주어야 한다.
            BFS(i, j)
            ans = max(ans, ice)

print(sum(map(sum, graph)))
print(ans)

for i in range(2 ** n):
    ice = 0
    for j in range(2 ** n):
        if graph[i][j] > 0 and not visited[i][j]:
            BFS(i, j)
            ans = max(ans, ice)