20058 - 마법사 상어와 파이어스톰

from collections import deque
import math
N, Q = map(int, input().split())
n = int(math.pow(2, N))
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
    
Llist = list(map(int, input().split()))

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

def rotate90(graph, length):
    temp = [[0]*length for _ in range(len(graph[0]))]
    for i in range(length):
        for j in range(length):
            temp[i][j] = graph[length-1-j][i]
    return temp 

def bfs(start):
    q =deque([start])
    total = 0; global n
    visited = [[False]*n for _ in range(n)]
    while q:
        border = q.popleft()
        r = border[0]
        c = border[1]
        visited[r][c] = True
        if graph[r][c] == 0:
            return 0
        total+=1
        for i in range(4):
            directionx = r + dx[i]
            directiony = c + dy[i]

            if (0<=directionx<n) and (0<=directiony<n) and (visited[directionx][directiony] == False) and (graph[directionx][directiony] != 0):
                q.append([directionx, directiony])
                visited[directionx][directiony] = True
                
    return total

#파이어스톰 완료
for L in Llist:
#     print("====================" + str(L) + "====================")
    # 부분격자의 가로/세로 길이
    l = int(math.pow(2, L))
    for row in range(0, n, l):
        for col in range(0, n, l):
            temp = graph[row:row+l]
            # 부분 행 가져오기
            for subCol in range(l):
                temp[subCol] = temp[subCol][col:col+l]

            newGraph = rotate90(temp, l)
            w = -1
            for a in range(row, row+l):
                w+=1; h = -1
                for b in range(col, col+l):
                    h+=1
                    graph[a][b] = newGraph[w][h]

    # 인접한 칸(동, 서, 남, 북)에 3개 미만 얼음이 0인 칸이 있으면 얼음의 양 1 줄임
    removeCandi = []
    for i in range(n):
        for j in range(n):
            moveList = []
            for k in range(4):
                r = i + dx[k]
                c = j + dy[k]
                if (0<=r<n) and (0<=c<n):
                    moveList.append([r, c])

            iceCnt = 0
            for rc in moveList:
                r = rc[0]
                c = rc[1]
                if graph[r][c] > 0:
                    iceCnt+=1

            if iceCnt<3:
                removeCandi.append([i, j])

    #이미 얼음이 없는 상태에서는 더이상 없앨 수 없음
    for rc in removeCandi:
        if graph[rc[0]][rc[1]] > 0:
            graph[rc[0]][rc[1]]-=1

# 남아있는 얼음의 합
iceTotalSum = 0
for r in range(n):
    iceTotalSum+=sum(graph[r])
print(iceTotalSum)

# 남아있는 얼음 중에서 가장 큰 덩어리가 차지하는 칸의 개수
remainIceSize = 0
for garo in range(n):
    for sero in range(n):
        remainIceSize = max(remainIceSize, bfs([garo, sero]))
        
print(remainIceSize)