https://www.acmicpc.net/problem/20058
"""
"""
from copy import deepcopy
from collections import deque
N, Q = map(int, input().split())
pan = [ list(map(int, input().split())) for _ in range(2**N) ]
L = list(map(int, input().split()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 부분격자 나누고 배열을 시계방향으로 90도 회전하는 코드 + 얼음이 있는 칸과 3개 이상 근접하지 않으면 해당 칸의 얼음 양을 -1하는 코드
for l in L:
if l == 0:
pan2 = deepcopy(pan)
else:
for i in range(0, 2**N, 2**l): # ★ 부분 격자 나누기 + 시계방향 90도 회전
for j in range(0, 2**N, 2**l):
t = [ pan[k][j:j+2**l] for k in range(i, i+2**l) ]
t = list(zip(*t[::-1]))
for x in range(2**l):
for y in range(2**l):
pan[x+i][y+j] = t[x][y]
pan2 = deepcopy(pan)
# pan2는 복제본이고, 필수적임 -> 얼음의 양이 반복문이 도는중에 실시간으로 -1이 되면 결과값에 이상이 생김
for i in range(2**N):
for j in range(2**N):
if pan2[i][j] > 0:
cnt = 0 # 얼음이 있는 칸과 근접한 개수
for k in range(4):
mx = i + dx[k]
my = j + dy[k]
if not (0 <= mx < 2**N and 0 <= my < 2**N):
continue
if pan2[mx][my] > 0:
cnt += 1
if cnt < 3:
pan[i][j] -= 1
# 남아있는 얼음의 합을 구하는 코드
def ice_sum():
ice_amount = 0
for i in range(2**N):
for j in range(2**N):
if pan[i][j] > 0:
ice_amount += pan[i][j]
return ice_amount
# 남아있는 얼음 중 가장 큰 덩어리가 차지하는 개수를 구하는 코드
def ice_big(x, y):
visited[x][y] = True
cnt = 1
q = deque([(x, y)])
while q:
px, py = q.popleft()
for k in range(4):
mx = px + dx[k]
my = py + dy[k]
if (0 <= mx < 2**N and 0 <= my < 2**N):
if pan[mx][my] > 0 and not visited[mx][my]:
visited[mx][my] = True
cnt += 1
q.append((mx, my))
return cnt
print(ice_sum()) # 남아있는 얼음의 합
answer = 0
visited = [ [False] * (2**N) for _ in range(2**N) ]
for i in range(2**N): # 남아있는 얼음 중 가장 큰 덩어리가 차지하는 개수
for j in range(2**N):
if pan[i][j] > 0:
answer = max(answer, ice_big(i, j))
print(answer)
배열의 시계방향 90도 회전 + BFS 탐색에 대한 문제