백준 1012번: 유기농 배추

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

 

from collections import deque
import sys
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def worm(x,y):
    que = deque()
    que.append((x,y))
    if graph[x][y]== 0:
        return False
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=h or ny>=w:
                continue
            if graph[nx][ny]==0:
                continue
            if graph[nx][ny]==1:
                    que.append((nx,ny))
                    graph[x][y]=0
                    graph[nx][ny]=0
    return True
n = int(input())
 
for _ in range(n):
    w, h, n = map(int, input().split())
    graph = [[0 for j in range(w)] for i in range(h)]
    count = 0
    for i in range(n):
        worm1, worm2 = map(int, sys.stdin.readline().split())
        graph[worm2][worm1]=1
    for x in range(h):
        for y in range(w):
            if worm(x,y) is True:
                count += 1
    print(count)