[python]白準1012有機白菜(BFS)

📌 質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.1本の白菜の上下左右4方向に異なる白菜がある場合は隣接しています.
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.0は白菜を植えていない土地を表し、1は白菜を植えた土地を表す.

入力

入力された第1行は、試験例の個数Tを与える.次の行から、各試験例について、第1行は、キャベツ栽培地の横長M(1≦M≦50)および縦長N(1≦N≦50)およびキャベツ栽培場所の個数K(1≦K≦2500)を与えた.次いでK行はハクサイの位置X(0≦X≦M−1),Y(0≦Y≦N−1)を与える.2つの白菜が同じ位置にある場合はありません.

しゅつりょく

各試験箱について、所望の最小白菜白ミミズ数を出力する.

入力例1

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

サンプル出力1

5
1

入力例2

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

サンプル出力2

2

📌 に答える

💬 Code

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x, y):
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 2
    return 1


for _ in range(int(input())):
    m, n, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]

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

    for i in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                cnt += bfs(i, j)

    print(cnt)

💡 Solution

cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt += bfs(i, j)

白菜を植えるところで修行する.bfsは隣接するすべての白菜を検査して1を返すために設計され,cnt+=bfs(i,j)は白菜領域を検査するたびにミミズを1匹添加する役割を果たした.

def bfs(x, y):
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 2
    return 1

白菜座標(x,y)が与えられた場合、白菜に隣接する白菜を表示します.方向ベクトルで上下左右の4つの位置に移動するために、for文を4回回転します.(nx,ny)は、その方向に1マス移動する座標である.(nx,ny)が座標系から離れず、白菜が植え込まれた座標である場合、その座標の隣接する白菜をキューに入れてナビゲートする.最後に、座標値を2に変更し、チェックしたことを示します(nx,ny).
bfsが終了すると、開始座標と隣接する白菜の座標値が2を上書きし、1を返し、1つの領域を表示します.