[白俊python]bfs/dfs-有機白菜

7258 ワード
アルゴリズム#アルゴリズム# 白駿 パイ テキストリンク
https://www.acmicpc.net/problem/1012

入力
入力された第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つの白菜が同じ位置にある場合はありません.
横長:M
垂直長:N
白菜の個数:K
BFSかDFSかを使います.
BFSはキューで解決したほうがよい.
これはDFSであり,直接キューを利用するのではなく,再帰を利用して解く.
に答える
import sys
sys.setrecursionlimit(10000)
t = int(input())

def dfs(x, y):
    if x <= -1 or x >= m or y <= -1 or y >= n:
        return 0
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return 1
    return 0

for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * n for _ in range(m)]
    for i in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1
        
    result = 0
    for j in range(m):
        for r in range(n):
            if dfs(j, r) == 1:
                result += 1
    print(result)
📌 ただし、実行中にエラーが発生し続けます.
調べてみましたが、さらに1000回呼び出すと、ランタイムエラーが発生します.
だから.
sys.setrecursionlimit(10000)
これを追加してすぐに解決しました
今日はたくさん勉強しました.
Androidのdistccベースの分散コンパイルと負荷分散の実現
mysql 8のプロファイル最適化