python 走迷宫问题

2744557306

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

; R6 D5 u9 b0 _+ O1 d6 P: n# L【输入格式】
0 S, Q: Y( w& m* a6 d) J# r) j
% Z+ w' y& S3 M/ C        第一行包含两个整数 n 和 m。
+ H) H5 U+ I( K* G$ ~/ r' d2 W9 E
+ J8 m7 A+ y+ Z- I. O        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
2 w+ O1 d; t9 M- i* v( W$ V
【输出格式】
2 a2 G! t+ H, [
/ g9 e7 l, {: [+ g0 z7 _% Z. X        输出一个整数，表示从左上角移动至右下角的最少移动次数。
0 P4 n/ i4 |4 N; X- x
  B: z/ a3 b0 k: C" H【数据范围】
# L+ g$ \- U# H4 n$ p+ r
/ m! {8 X+ m8 J" l' q: g9 C0 w1 Q        1≤n,m≤100

【输入样例】

5 5
$ y! O, F7 g- a, R0 1 0 0 0
/ O* ?3 u& [! h& V0 b! M0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
, H) ]4 I( d# t% W0 y5 R0 0 0 1 0
【输出样例】
' J9 B" O4 n6 h* m; {4 i! J
8
; u/ E$ {4 a& i3 v  A 【解题思路】
' V# r' ^+ Q& E
        BFS的典中典。

1. from collections import *
   , V: }1 K& T& [/ G8 @
2. n,m = map(int,input().split())5 w( ?. Z( T! F. I5 w7 H- Y
   
3. mp = [[0]*(m+5)]
   ; o& d9 _! @/ h) S: i\" N
4. for i in range(n):9 y: v  z* F% @
   
5.     mp.append([0]+list(map(int,input().split())))
   3 E. d8 L  F) L3 z\" R: r2 m; g\" q: E
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]. s7 L\" p7 U6 _/ p
   
7. st = [[0]*(m+5) for _ in range(n+5)]\" u\" F- N0 ^+ U
   
8. def bfs():
   2 K0 {$ ^3 S5 V2 _+ q7 Z
9.     q = deque()
   9 h8 {7 w# _4 g8 I
10.     q.append([1,1,0])- d% x# ^2 [) d7 e' A
    
11.     st[1][1]=10 Y9 _+ Q- s% B: g- p% W$ o' M- p
    
12.     while q:7 n2 Z\" W  B9 c* Q  C. |& [\" M7 f! r* M
    
13.         tx,ty,step = q.popleft()
    ; g7 t! D: O  R, f& b
14.         if tx==n and ty==m:
    - ^; x8 h5 O0 a
15.             print(step)
      ]& ^4 f% t, A; |0 p0 h) _9 @
16.             return8 d2 O. Y' Z4 W  z
    
17.         for x_,y_ in dir:
    0 q  i/ ^. C4 q! B
18.             nx,ny = tx+x_,ty+y_0 M) B- Q8 V$ i0 c8 Q$ X
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    1 K7 [0 n& z- i+ p5 b\" r' S
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    + }( k0 o6 u  f! p
21.             q.append( [nx,ny,step+1] )
    ! Z9 g! I0 o( J) l1 d2 @
22.             st[nx][ny]=1
    # P( n; f; |5 Q' \) Q& N. i4 {8 a# Z
23. bfs()

复制代码