BOJ 1012有機白菜

1592 ワード
2021.01.07 テキストリンク
https://www.acmicpc.net/problem/1012
1秒、512 MBメモリ
input :
  • 試験盤箱数T
  • 横長M,縦長N,ハクサイ栽培位置の個数K(1<=M,N<=50)(1<=K<=2500)
    • .
  • 白菜の位置X,Y(0<=X<=M-1),(0<=Y<=N-1)
    • output :
    出力
  • で最も少ない白菜白ミミズの数.
    • 条件:
  • 白菜の上下左右にそれぞれ1つの白菜があり、隣接しているとみなされます.
  • 本の白菜を数えるパーティー.
  • 白菜がある1、ない024579182
    BOJ 4963島と同じ数の問題
    必要な変数.
    空のグラフ(白菜の位置を示す)、visitは必要ありません
    DFSを入力した回数はarlycnt変数3個です.
    BFSで解決することもできますが、DFSで解決したばかりなのでDFSで解決しましょう.
    に対する拘束が不十分です.
    DFS関数.△1人を0に変えましょう.
    正しいコード:
    import sys
sys.setrecursionlimit(10000)

T = int(sys.stdin.readline())
ans = []

def DFS(navi, position):
    navi[position[0]][position[1]] = 0

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

    for i in range(len(dx)):
        nx = position[0] + dx[i]
        ny = position[1] + dy[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
            continue
        if navi[nx][ny]:
            DFS(navi, [nx, ny])

for _ in range(T):
    m, n, k = map(int, sys.stdin.readline().split())
    graph = [[0] * m for _ in range(n)]

    for i in range(k):
        y, x = map(int, sys.stdin.readline().split())
        graph[x][y] = 1

    cnt = 0

    for x in range(n):
        for y in range(m):
            if graph[x][y]:
                DFS(graph, [x, y])
                cnt += 1

    ans.append(cnt)

for data in ans:
    print(data)
    • Java同時プログラミングSemaphore
    [TIL] CSS Flex,Grid