1012号:有機白菜(Python,Python)

プール(1)

import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs(vy, vx):
  for i in range(4):
    y = vy + dy[i]
    x = vx + dx[i]
    if M[y][x] == 1:
      M[y][x] = 0
      bfs(y,x)

for _ in range(t):
  m, n, k = map(int, sys.stdin.readline().split())
  M = [[0]*(m+2) for _ in range(n+2)]
  for i in range(k):
    x, y = map(int, sys.stdin.readline().split())
    M[y+1][x+1] = 1
  
  cnt = 0
  for i in range(1, n+1):
    for j in range(1, m+1):
      if M[i][j] == 1:
        M[i][j] = 0
        bfs(i,j)
        cnt += 1
  
  print(cnt)

bfsを適用して白菜地(M)を作成し、ダブルfor文を使用して確認位置の値を0に変更します.
時間:76ミリ秒
コード長:599 B

プール(2)

import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs(L):
  for i in range(4):
    x = L[0] + dx[i]
    y = L[1] + dy[i]
    if ([x, y] in A):
      A.remove([x, y])
      bfs([x,y])

for i in range(t):
  m, n, k = map(int, sys.stdin.readline().split())
  A = []
  for i in range(k):
    x, y = map(int, sys.stdin.readline().split())
    A.append([x, y])

  cnt = 0
  while A:
    bfs(A.pop(0))
    cnt += 1

  print(cnt)

白菜畑(M)を作成しないで、白菜の位置の配列(A)を作成して、bfsを適用します
時間:296ミリ秒
コード長:486 B
*リストの追加/削除に時間がかかる