[Baekjoon] -2178. 迷宮を探る



バックアップ-問題リンク
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)を与えた.