python 走迷宫问题

2744557306

题目描述】

        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
3 a9 y, h: c, y- ^7 P( _
【输入格式】
# q' }2 V- h$ ]4 J- x/ K; |
        第一行包含两个整数 n 和 m。

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

7 \3 T4 P' H( p. t【输出格式】
# Q0 [- W5 V/ N9 L
' m9 G* C2 X' B! t" ?: K6 `7 a/ H; M" M        输出一个整数，表示从左上角移动至右下角的最少移动次数。
- G3 L/ y! W7 d
6 g4 U6 H" Z( }【数据范围】

; O+ d: F" c! Y/ ?9 Y        1≤n,m≤100

【输入样例】

! g+ y& o9 ], I1 e0 q6 p% J& Q5 5
4 {- F: b& Y1 J, b* r3 o( \6 [0 1 0 0 0
7 E  }3 Z7 [$ T0 1 0 1 0
0 0 0 0 0
" [* ~( w- l9 H( i8 _! z  m0 1 1 1 0
0 0 0 1 0
【输出样例】
3 q6 G$ ^( a" w& u
8
1 {9 S- j; T7 g8 | 【解题思路】
/ P# z+ U( V; J: u8 W5 ^" j
' n' ^' I8 ]  X/ l& A( a8 h1 I! x$ \        BFS的典中典。

1. from collections import *) m2 M% J, ?/ B0 @) M/ Y
   
2. n,m = map(int,input().split())
   : i- V+ Z6 ]2 W! U! O2 Q9 p
3. mp = [[0]*(m+5)]
   0 O/ T* f) w3 p7 M  S  p
4. for i in range(n):( r; G  r; o, P4 g( R+ T; v
   
5.     mp.append([0]+list(map(int,input().split())))
   0 h3 a4 O3 W4 ~$ q! l$ S
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   ' F$ s/ a5 f6 L  a* b3 P
7. st = [[0]*(m+5) for _ in range(n+5)]
   8 L% ~/ p\" l- z
8. def bfs():8 r3 a7 [/ V9 L2 x9 b- b6 q$ b
   
9.     q = deque()
   * L. X$ D( ]$ o) T
10.     q.append([1,1,0])! H- w$ D2 ]! s7 P) E\" F
    
11.     st[1][1]=1) [0 X: }7 a- S
    
12.     while q:
    1 m$ G5 H2 |  A, w3 M
13.         tx,ty,step = q.popleft()$ |  _5 J& n6 w7 N
    
14.         if tx==n and ty==m:
    / U3 m$ P  m1 u1 O+ p9 v$ [
15.             print(step)/ z! R$ N3 q6 J8 w) Z0 f9 S
    
16.             return
    1 D# k! f- Y8 Q) a. i
17.         for x_,y_ in dir:
    ( R# ]  P! ^+ J
18.             nx,ny = tx+x_,ty+y_; @5 I9 X+ G7 k6 E
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue1 N& V8 t/ o, T, O
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    \" Y2 \\" Q3 t4 N& x( l+ D* \
21.             q.append( [nx,ny,step+1] )+ E/ ?# G: Q# Q( S9 N7 ]  e
    
22.             st[nx][ny]=10 f6 g6 ?& h. s' o# ~9 C3 \
    
23. bfs()

复制代码