[伯俊]迷宮探索/2178/Python/PSN/BFS

💡質問する

N×Mサイズの配列として表現された迷路があります.

迷路では、1は移動可能なセル、0は移動不可能なセルを表します.これらの迷路が与えられた場合、(1,1)から(N,M)の位置に移動する際に通過しなければならない最小セル数を求めるプログラムを作成します.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.
上記の例では、(N,M)の位置に移動するには15格子を通過しなければならない.数欄には、開始位置と到達位置も含まれます.

入力

第1行は2つの整数N,M(2≦N,M≦100)を与える.次のN行には迷路としてM個の整数がある.各数を入力として加算します.

しゅつりょく

出力は最初の行の最小セル数を通過する必要があります.常に到着位置まで移動できる場合のみ、入力として使用されます.
入力例

4 6
101111
101010
101011
111011

サンプル出力

15

📖私が書いたコード

from collections import deque
n,m=map(int,input().split())
maze=[list(map(int,input())) for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
dq=deque()
def BFS(x,y):
    dq.append((x,y))
    while dq:
        p,q=dq.popleft()
        for i in range(4):
            nx=p+dx[i]
            ny=q+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if maze[nx][ny]==1:
                maze[nx][ny]=maze[p][q]+1
                dq.append((nx,ny))
BFS(0,0)
print(maze[n-1][m-1])

質問元:https://www.acmicpc.net/problem/2178