python 走迷宫问题

2744557306

题目描述】
$ ]. h* h" l( L/ n. |  j; P
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
) `6 H3 @$ w* f
2 g$ _9 D, X4 `% ^: k【输入格式】

        第一行包含两个整数 n 和 m。

        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

/ D% h) T* S: r% C" P2 g# N) @【输出格式】
2 d/ ]% e: U# q' j8 f  V0 H$ c
        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】
* |: k! @9 E0 a  X' ^2 O
! k% B6 T2 Q  u) u+ ]& D! j        1≤n,m≤100

8 F% H$ n  r  t; q# I  O【输入样例】
( F$ F4 n/ B! R( Q
5 5
* ~( k; O& K8 E* ?+ ^3 c$ g' q9 \0 1 0 0 0
4 r$ x8 i5 Q& f- C- Y. S3 S3 U( m9 J0 1 0 1 0
( }4 |* @& N4 U0 \  l! h4 f0 G0 0 0 0 0
1 _1 _8 O2 E+ n9 A- w0 1 1 1 0
# o4 u& q1 b5 p1 p' k" U, }6 P& \3 _0 0 0 1 0
5 x" k, V% ~- r; r% {; p& H【输出样例】

8
【解题思路】
; i; x& E3 t" \; s" V" B
) w  E! T. A. c        BFS的典中典。

1. from collections import *, X% ~7 }. ]5 O6 ?0 A% v
   
2. n,m = map(int,input().split())+ Z9 k, O1 E/ @4 u
   
3. mp = [[0]*(m+5)]
   - X\" ]6 U0 [7 w\" X\" F* p) X$ z. w\" b
4. for i in range(n):% c0 n0 a* I; Q! }
   
5.     mp.append([0]+list(map(int,input().split())))
   ! j7 ^  P( c2 O7 j* g# f3 [
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   / _# L; b, |7 e; S$ y# p, K
7. st = [[0]*(m+5) for _ in range(n+5)]
   & o& t9 D- L* Z& V8 M. Q  X: J
8. def bfs():
   / f1 Y8 C4 I4 H
9.     q = deque()3 _3 ~5 }5 I\" M3 W, o
   
10.     q.append([1,1,0])# w* P; N6 G0 ]8 U* j- W9 B6 E
    
11.     st[1][1]=1
    . J  F& N- j\" w- d/ H, P4 ~
12.     while q:! k+ O* b2 N( j  }
    
13.         tx,ty,step = q.popleft()\" k4 W( Z! Y- \4 [) x/ V
    
14.         if tx==n and ty==m:8 D! `' F9 i+ Y! a, i
    
15.             print(step): q. |$ A* X+ y: H0 ?
    
16.             return. A3 V' o/ B! j# x3 f
    
17.         for x_,y_ in dir:/ b3 v, C7 S' q5 v( Y7 n
    
18.             nx,ny = tx+x_,ty+y_; T4 B+ x7 i: Y  v\" g. E! i/ P) d
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue0 L  s  }7 _% b  B% k
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    $ E; _% S' f& S\" b  ]: W
21.             q.append( [nx,ny,step+1] )
    3 ~& T, Z! g6 f5 T
22.             st[nx][ny]=1
    $ z4 {$ f# O7 Q+ ~% S6 c
23. bfs()

复制代码