[白俊]2178号-探索迷宮
📩 ソース
質問する
N×Mサイズの配列として表現された迷路があります.
迷路では、1は移動可能なセル、0は移動不可能なセルを表します.これらの迷路が与えられた場合、(1,1)から(N,M)の位置に移動する際に通過しなければならない最小セル数を求めるプログラムを作成します.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.
上記の例では、(N,M)の位置に移動するには15格子を通過しなければならない.数欄には、開始位置と到達位置も含まれます.
入力
第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.
しゅつりょく
出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.
👉 の意見を打診
visited配列が生成される
def bfs():
q = [[0,0]]
visited[0][0] = 1
while q:
i, j = q.pop(0)
for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < m and maze[ni][nj] == 1 and visited[ni][nj] == 0:
q.append((ni,nj))
visited[ni][nj] = visited[i][j] + 1
return visited[n-1][m-1]
n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
print(bfs())Reference
この問題について([白俊]2178号-探索迷宮), 我々は、より多くの情報をここで見つけました https://velog.io/@letgodchan0/백준-2178번-미로-탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol