Untitled
unknown
python
3 years ago
2.8 kB
8
Indexable
from collections import deque
from sys import stdin
input = stdin.readline
N, Q = map(int,input().split())
field = [ list(map(int,input().split())) for _ in range(pow(2,N)) ]
L = list(map(int,input().split())) # 2^L x 2^L 만큼의 sub array if L = 0 => 1 x 1
outBound = pow(2,N)
mv = [[0,1],[1,0],[0,-1],[-1,0]]
def rotateSubarray( cur_y:int, cur_x:int, step:int):
global outBound, field
Length = pow(2, step)
new_field = [[0 for _ in range(outBound)] for __ in range(outBound)]
for y in range(cur_y, outBound, Length):
for x in range(cur_x, outBound, Length):
for l in range(Length):
for q in range(Length):
new_field[y + q][x + Length - l -1] = field[y+l][x+q]
field = new_field
melting = deque([])
for row in range(outBound):
for col in range(outBound):
cnt = 0
for dir in range(4):
ny, nx = row + mv[dir][0], col + mv[dir][1]
if(ny<0 or nx<0 or nx>=outBound or ny>=outBound): continue
if(field[ny][nx]!=0):
cnt+=1
if(cnt<3 and field[row][col]!=0):
melting.append((row,col))
while(len(melting)):
y, x = melting.popleft()
field[y][x]-=1
return
vis = [ [False for _ in range(outBound)] for __ in range(outBound)]
def bfs(cur_y:int, cur_x:int):
global outBound
place = deque([(cur_y,cur_x)])
cnt = 1
S = field[cur_y][cur_x]
vis[cur_y][cur_x] = True
while(place):
cur_y, cur_x = place.popleft()
for dir in range(4):
ny, nx = cur_y + mv[dir][0], cur_x + mv[dir][1]
if(0>ny or 0>nx or ny>=outBound or nx>=outBound):
continue
if(not vis[ny][nx] and field[ny][nx]):
vis[ny][nx]=True
S += field[ny][nx]
cnt += 1
place.append((ny,nx))
return cnt, S
for i in range(Q):
rotateSubarray(0,0,L[i])
# another = rotate_and_melting(another,outBound,0)
# 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다.
# 파이어스톰은 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다.
# 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
# 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
res = 0
M = -1
flag = False
for i in range(outBound):
for j in range(outBound):
if(field[i][j] >0 and not vis[i][j]):
flag = True
tmp, S = bfs(i,j)
res += S
M = max(tmp,M)
if(not flag):
print(0)
print(0)
else:
print(res)
print(M)
Editor is loading...