python 走迷宫问题

2744557306

题目描述】
/ y# F3 m9 t7 u  N7 W
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
* H! D: ^; Y) n
【输入格式】

0 L* O* t+ b4 ^2 `  [% F        第一行包含两个整数 n 和 m。

) U: P5 l! u, O: I        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

【输出格式】
0 ]5 i7 |5 P5 C1 X7 N, v1 h3 I
        输出一个整数，表示从左上角移动至右下角的最少移动次数。
3 w" L  R: U, p+ d0 q" t3 |6 i
- M5 t: J6 b: U1 ]- d【数据范围】
5 L/ m4 g; q5 f- ~1 Q, g# g8 I3 @1 u
! T3 j  d" n# A* E  U/ `! a        1≤n,m≤100

【输入样例】

3 ]/ g" \# ~" S5 5
4 N( k% k" X; ]! s0 1 0 0 0
0 1 0 1 0
) A$ V* z7 \: w0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
/ R* P4 [0 g8 v2 F0 L* `9 T【输出样例】

8
【解题思路】
" @. L5 E" i1 a* Y% L7 {  c
        BFS的典中典。

1. from collections import *
   ( f' D: w\" g6 S% y5 s7 _& E9 v# D
2. n,m = map(int,input().split())1 U9 p# Y* P- y\" N1 {
   
3. mp = [[0]*(m+5)]: q9 m; ]+ R# q- `3 K! P
   
4. for i in range(n):
   - b\" v5 p% B! G
5.     mp.append([0]+list(map(int,input().split())))
   2 d6 |( q7 o2 M& d' z- U3 U' m2 X\" }/ `6 t
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]2 E9 _4 _6 m; C( ]0 P) }  [
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   ; H( K3 E- b; S
8. def bfs():
   ( _% l' r( q- B. f/ d
9.     q = deque()
   & X3 a8 R- Z# N3 m, g! V/ X0 j( I
10.     q.append([1,1,0])+ Z# K, W  T, _$ H% [+ Q, o
    
11.     st[1][1]=1. x0 h  T4 S\" T0 }! @3 r  O
    
12.     while q:
    6 c8 x* N- `; \1 K/ q
13.         tx,ty,step = q.popleft()
    1 R' K4 S1 C) D\" A
14.         if tx==n and ty==m:$ y% v4 {( T4 ~, g( W  J4 q
    
15.             print(step)1 {\" u8 v! {\" A/ |
    
16.             return2 C# o$ Q/ q( z: v\" s% Q0 m
    
17.         for x_,y_ in dir:$ }+ u! d' ~9 m- j1 p) m
    
18.             nx,ny = tx+x_,ty+y_
    - [2 t3 a\" \\" S1 e- {0 p1 u
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    , D1 D* f) e\" f. _
20.             if mp[nx][ny]==1 or st[nx][ny]:continue+ t7 O  i0 a. x' j, ~
    
21.             q.append( [nx,ny,step+1] ). p  d# q+ G; D$ x7 c0 O5 D- F
    
22.             st[nx][ny]=1  o6 ^, r5 u- M* S
    
23. bfs()

复制代码

+ a0 o9 {, o$ F, s2 s/ u