[白俊]2012号:有機白菜(Python)



質問する



私の答え

from collections import deque #bfs 풀

t=int(input())

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    que=deque()
    que.append((x,y))
    arr[x][y]=0

    while que:
        xx,yy=que.popleft()#배추가 있는 곳 좌표
        for i in range(4):#상하좌우 탐색
            nx=xx+dx[i]
            ny=yy+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and arr[nx][ny]==1:
                #범위를 만족하고 배추가 있다면
                que.append((nx,ny))#덱큐에 추가하고
                arr[nx][ny]=0#0으로 변경
            
        

for i in range(t):
    m,n,k=map(int,input().split())#가로 세로 개수
    arr=[[0]*m for ii in range(n)]#밭 생성
    cnt=0#벌레 개수==구역의 수
    
    for j in range(k):
        x,y=map(int,input().split())#좌표
        arr[y][x]=1#배추가 있는 곳 표시, 행과 열 주의

    for a in range(n):#배추가 있는지 없는지 검사
        for b in range(m):
            if arr[a][b]==1:#있다면
                bfs(a,b)#탐색
                cnt+=1#개수 증가
    print(cnt)
方法
  • bfsで問題解決器dequeを解く.
  • 白菜があるところは1,白菜がないところは0,探索後は1を0に変更する.
  • bfsなので、y値を基準に横探索を行うので、白菜がいる場所はarr[y][x]です.
  • 幅*奥行きm×nm\times nm×nの範囲内に白菜があればQに加えて0に変更することができます.