[Baekjoon] -2178. 迷宮を探る
8132 ワード
バックアップ-問題リンク
import sys
def bfs(r, c):
global result
Q.append([r, c])
visited[r][c] = 1
while Q:
temp = Q.pop(0)
for i in range(4):
nr = temp[0] + dx[i]
nc = temp[1] + dy[i]
if 0 <= nr < N and 0<= nc < M:
if maze[nr][nc] == '1' and visited[nr][nc] == 0:
visited[nr][nc] = visited[temp[0]][temp[1]] + 1
if nr == N-1 and nc == M-1:
result = visited[nr][nc]
return result
Q.append([nr, nc])
return result
N, M = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
Q = []
result = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
print(bfs(0, 0))
🔑 これは典型的なbfs問題である.セルを数えるときには開始位置と到達位置も含まれるので、距離値の調整に注意しましょう~!
問題では(1,1)から始まるべきで,インデックス値が0から始まる開始位置(0,0)を与えた.
Reference
この問題について([Baekjoon] -2178. 迷宮を探る), 我々は、より多くの情報をここで見つけました https://velog.io/@jjiani/Baekjoon-2178.-미로-탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol