1012号:有機白菜(Python,Python)
1378 ワード
プール(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
*リストの追加/削除に時間がかかる
Reference
この問題について(1012号:有機白菜(Python,Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@offr8m/1012-유기농-배추テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol