りんごの木(BFS)
8690 ワード
作成日:2022年2月14日午後4:37
メッシュボードの中央座標からキューに入れます. dequeueを通過した座標の上下左右のノード(座標)をキューに再配置し、これを繰り返します. ch配列でチェックノードかどうかを確認します. 複文が終了するとL(レベル)はn/2となる.例えば、nが5である場合、Lが2である場合、繰り返し文を停止し、ダイヤモンド形状でメッシュプレートを探索し、完成させることができる.
インプリメンテーションコード
# 사과나무 (BFS)
import sys
from collections import deque
#sys.stdin = open("input.txt", "rt")
def BFS():
L = 0
total = farm[n//2][n//2]
while True:
if L == n//2:
break
size = len(Q)
for i in range(size):
tmp = Q.popleft()
for j in range(4):
x = tmp[0]+dx[j] # x좌표
y = tmp[1]+dy[j] # y좌표
if ch[x][y] == 0:
total += farm[x][y]
ch[x][y] = 1
Q.append((x,y))
L += 1
print(total)
if __name__ == "__main__":
n = int(input())
farm = []
for _ in range(n):
row = list(map(int, input().split()))
farm.append(row)
# 시계방향 좌표
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ch = [[0 for _ in range(n)] for _ in range(n)]
Q = deque()
Q.append((n//2, n//2)) # 중앙부터 시작
ch[n//2][n//2] = 1
BFS()
Reference
この問題について(りんごの木(BFS)), 我々は、より多くの情報をここで見つけました https://velog.io/@lsj8706/사과나무-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol