python 走迷宫问题

2744557306

题目描述】
( K$ P" z' e) Y* c: H( A1 \9 Y
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

# Z1 `7 Z' v) a; c6 c1 H【输入格式】
4 M& s* F6 \- ?% F
* s$ E$ ]5 d! K        第一行包含两个整数 n 和 m。
0 A# S6 }9 ^$ w6 l) @9 c, W, a. Y7 K
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
2 |! x! Y# r& q
【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
( P5 m' G! f4 R, ?$ V
5 `; t% y& c& z" [/ k" \5 ^( b/ X【数据范围】
, J% a1 {" b3 d4 j+ ~% g
; z% O* b" M. d        1≤n,m≤100
  q0 n$ t; ~0 S5 c
" s' |% r; `3 v) q【输入样例】
' x& k1 L5 z/ M9 Z0 V0 \; c
5 5
4 {+ q) d: c  l& c0 a6 h$ x0 1 0 0 0
0 1 0 1 0
7 I! q2 N/ D6 D0 N0 0 0 0 0
' V# V* E& |0 ?& J* d0 1 1 1 0
& R4 ^) A; F: i/ F# w0 0 0 1 0
【输出样例】
" {4 t2 k  _7 P
, S' u' ~6 }6 N" ^/ _* Z8
【解题思路】
9 [1 Y- u4 e3 d) t) H* V3 r
        BFS的典中典。

1. from collections import *7 s! q$ K) }# f
   
2. n,m = map(int,input().split())
   / g, n; F- ?( R, r9 d8 g5 j( _
3. mp = [[0]*(m+5)]
   * Q# s, P4 D2 w  Z
4. for i in range(n):\" K0 {\" S' K\" d8 V6 e4 h* L! X
   
5.     mp.append([0]+list(map(int,input().split())))0 q( S# d/ v( a; }$ a/ Z
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]3 M+ U/ U& v# K% \2 F\" F. u$ l
   
7. st = [[0]*(m+5) for _ in range(n+5)]  P4 T0 G+ S: k
   
8. def bfs():8 z1 U  D0 e$ c
   
9.     q = deque()& u# h5 h+ e4 v4 ^/ s/ [. X2 ?
   
10.     q.append([1,1,0])8 P/ m/ u5 u. x0 K: }! q( |& _
    
11.     st[1][1]=1
    2 k: F0 a5 B  e' @+ I0 H\" O7 R% M5 M
12.     while q:. M\" c' p1 m4 I& H0 Q* J
    
13.         tx,ty,step = q.popleft()  @& ]- A8 M) I
    
14.         if tx==n and ty==m:
    9 l; [  Q( w2 e6 Y4 l7 d$ d9 j
15.             print(step)
    1 P: a0 [2 U3 y& c
16.             return
    ! d5 u6 }\" H1 d. y\" ]
17.         for x_,y_ in dir:
    0 Y% Y! j( ~# Q\" m; U! e
18.             nx,ny = tx+x_,ty+y_1 M( J- h, L' s( B2 a
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue+ l7 l/ E$ ^1 N- [0 B* d8 I. \( F
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue  n) ]) p0 s! V\" M
    
21.             q.append( [nx,ny,step+1] )& g0 U  f) k# p
    
22.             st[nx][ny]=13 C3 W6 [, X0 q* H% X9 E1 O
    
23. bfs()

复制代码

- c0 F' E$ A/ V- V