글 읽기 - python 코드입니다!

dprjsgml 2년 전 0

dfs부분에서 이런식으로 풀면 왜 예제 5번에 덩어리가 59개로 나올까요 ㅠㅠ 이해가안가네요

import sys
sys.setrecursionlimit(10**5)
from copy import deepcopy
n,q=map(int,input().split())
arr=[list(map(int,input().split())) for i in range(2**n)]
l=list(map(int,input().split()))
ice_leng=2**n
dx=[0,0,-1,1]
dy=[-1,1,0,0]
visited=[[0 for _ in range(ice_leng)] for _ in range(ice_leng)]
result=0

def rotate(ice_leng,grid_leng):
    global arr
    arr1=deepcopy(arr)
    for i in range(0,ice_leng,grid_leng):
        for j in range(0,ice_leng,grid_leng):
            for r in range(grid_leng):
                for c in range(grid_leng):
                    arr[i+r][j+c]=arr1[i+grid_leng-1-c][j+r]

def border():
    global arr,ice_leng,cnt
    cnt=[[0]*ice_leng for i in range(ice_leng)]
    for i in range(ice_leng):
        for j in range(ice_leng):
            if arr[i][j]!=0:
                for k in range(4):
                    nx=i+dx[k]
                    ny=j+dy[k]
                    if 0<=nx<ice_leng and 0<=ny<ice_leng and arr[nx][ny]!=0:
                        cnt[nx][ny]+=1

def dfs(i,j,mass):
    global ice_leng,visited,result
    visited[i][j]=1
    for k in range(4):
        nx=i+dx[k] 
        ny=j+dy[k]           
        if 0<=nx<ice_leng and 0<=ny<ice_leng and arr[nx][ny]!=0 and visited[nx][ny]==0:
            mass+=1
            result=max(result,mass)
            dfs(nx,ny,mass)

            
for k in range(q):
    grid_leng=2**l[k]
    rotate(ice_leng,grid_leng)
    border()
    for i in range(ice_leng):
        for j in range(ice_leng):
            if arr[i][j]>0 and cnt[i][j]<3:
                arr[i][j]-=1
               

for i in range(ice_leng):
    for j in range(ice_leng):
        if arr[i][j]!=0:
            dfs(i,j,1)


ice_hap=0
for i in range(ice_leng):
    ice_hap+=sum(arr[i])

print(ice_hap)
if result!=0:
    print(result)
else:
    print(0)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 코드입니다!

dprjsgml 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말