Untitled
unknown
python
2 years ago
2.8 kB
4
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...