[伯俊]2012号-有機白菜

📩 ソース

質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.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つの白菜が同じ位置にある場合はありません.

しゅつりょく

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

👉 の意見を打診

bfsまたはdfsを介して探索する方法を考えた.二重配列では,1上下左右に集まり,存在する箇所で個数を求めればよい.

の二層配列の値が1visitedの値が0の場合、幅優先探索または深さ優先探索により、上、下、左、右に到達可能なすべての位置を見つけ、visitedの値を1に変換する.

はvisitedの値を変更するだけなので、二層配列では、新しい領域の1に遭遇するたびにdfsまたはbfs関数を実行し、visitedの値を変更してanswer(배추희지렁이의 수)を1増加させる!

# dfs로 풀기
def dfs(i, j):
    visited[i][j] = 1
    for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
        ni, nj = i + di, j + dj
        if 0 <= ni < n and 0 <= nj < m and arr[i][j] == 1 and visited[ni][nj] == 0:
            dfs(ni, nj)

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(k)]
    arr = [[0] * m for _ in range(n)]
    visited = [[0] * m for _ in range(n)]
    for i, j in data:
        arr[j][i] = 1
    answer = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1 and visited[i][j] == 0:
                dfs(i, j)
                answer += 1
    print(answer)

ただし、上記のdfsを使用してコードを実行すると、ランタイムエラーが発生します.基本的に復帰回数が限られているので、制限範囲を増やす方法が必要です.

sysモジュールを介してinputを受信する場合は、我が耳の制限範囲の値を入力すればよい.

すなわちsys.setrecursionlimit(재귀 횟수)と入力すればよい.

# dfs로 풀기
def dfs(i, j):
    visited[i][j] = 1
    for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
        ni, nj = i + di, j + dj
        if 0 <= ni < n and 0 <= nj < m and arr[i][j] == 1 and visited[ni][nj] == 0:
            dfs(ni, nj)

import sys
sys.setrecursionlimit(111111)
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(k)]
    arr = [[0] * m for _ in range(n)]
    visited = [[0] * m for _ in range(n)]
    for i, j in data:
        arr[j][i] = 1
    answer = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1 and visited[i][j] == 0:
                dfs(i, j)
                answer += 1
    print(answer)

# bfs로 풀기
def bfs(i, j):
    q = []
    q.append((i, j))
    visited[i][j] = 1
    while q:
        i, j = q.pop(0)
        for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m and arr[i][j] == 1 and visited[ni][nj] == 0:
                visited[ni][nj] = 1
                q.append((ni, nj))
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(k)]
    arr = [[0] * m for _ in range(n)]
    visited = [[0] * m for _ in range(n)]
    for i, j in data:
        arr[j][i] = 1

    answer = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1 and visited[i][j] == 0:
                bfs(i, j)
                answer += 1
    print(answer)