282. 마법사 상어와 파이어스톰

백준

1. Python

from copy import deepcopy
from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

n, q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(2 ** n)]
ll = map(int, input().split())

for l in ll:
    if l > 0:
        for i in range(0, 2 ** n, 2 ** l):
            for j in range(0, 2 ** n, 2 ** l):
                t = [a[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):
                        a[x + i][y + j] = t[x][y]
        b = deepcopy(a)
    if l == 0:
        b = deepcopy(a)

    for x in range(2 ** n):
        for y in range(2 ** n):
            cnt = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if not 0 <= nx < 2 ** n or not 0 <= ny < 2 ** n:
                    continue
                if b[nx][ny] > 0:
                    cnt += 1
            if cnt < 3 and b[x][y] > 0:
                a[x][y] -= 1

ans1 = sum(sum(s) for s in a)
print(ans1)

c = [[0] * (2**n) for _ in range(2 ** n)]
q = deque()
ans2 = 0
for i in range(2 ** n):
    for j in range(2 ** n):
        if a[i][j] != 0 and c[i][j] == 0:
            q.append([i, j])
            c[i][j] = 1
            cnt = 1
            while q:
                x, y = q.pop()
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < 2 ** n and 0 <= ny < 2 ** n:
                        if a[nx][ny] != 0 and c[nx][ny] == 0:
                            cnt += 1
                            c[nx][ny] = 1
                            q.append([nx, ny])
            ans2 = max(ans2, cnt)

print(ans2)