[9/2]有機白菜


シルバー2 質問する

マイコード

import sys
sys.setrecursionlimit(10000)

t = int(input())

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

    move_x = [1, -1, 0, 0]
    move_y = [0, 0, 1, -1]

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

    def dfs(x, y):
        arr[x][y] = 0
        for i in range(4):
            dx = x + move_x[i]
            dy = y + move_y[i]

            if (dx < 0 or dx >= m or dy < 0 or dy >= n ):
                continue
            if (arr[dx][dy] == 1):
                dfs(dx, dy)
        return True

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

    print(cnt)

ろんり

  • dfs
  • を使用
  • 復帰、sys.setrecursionlimit(10000)を使用しました.
  • その他のコード(ネイティブ方式)

    import sys
    sys.setrecursionlimit(10000)
    
    t = int(input())
    
    for _ in range(t):
        m, n, k = map(int, input().split())
        arr = [[0] * n for _ in range(m)]
        for _ in range(k):
            a, b = map(int, input().split())
            arr[a][b] = 1
    
        def dfs(x, y):
            
            if (x < 0 or x >= m or y < 0 or y >= n ):
                return False
            
            if (arr[x][y] == 1):
                arr[x][y] = 0
                
                dfs(x-1, y)
                dfs(x+1, y)
                dfs(x, y-1)
                dfs(x, y+1)
                return True
            
            return False
            
        cnt = 0
        for i in range(m):
            for j in range(n):
                if (dfs(i, j) == True):
                    cnt += 1
                    
        print(cnt)

    フィードバック


    4つの
  • 関数を使用した.