python 走迷宫问题

2744557306

题目描述】
& a; a1 J# Z/ C7 D
( \1 ]0 L# G: u4 B5 N! L        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
9 w* F7 Z, ~# O1 K
( u4 u* Y3 }' Y【输入格式】
% k0 X" D# d6 M2 {( ]
        第一行包含两个整数 n 和 m。
% Q4 N, z& }# A& l
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

, `; z: A- N5 T( J【输出格式】
/ ~0 F/ O- O) @3 M+ n
; ~1 {7 o; R7 `3 t) b: L2 V        输出一个整数，表示从左上角移动至右下角的最少移动次数。

/ p7 m( W" @1 E【数据范围】
5 z* T: ], B  X$ |0 }+ c
        1≤n,m≤100
9 A: \5 l, O& r# L* J8 g, q
【输入样例】
: a, v( j* P0 H, t/ ?0 P
5 5
0 1 0 0 0
8 ~; c- v. F4 |  P* ~0 W5 ?1 `# s0 1 0 1 0
; A' B8 k" Q6 V! N. Z3 b0 0 0 0 0
6 R  C2 p) }" X, F; ]; c0 1 1 1 0
0 0 0 1 0
* ]' q& P3 }$ p1 t2 ?. P【输出样例】

8
【解题思路】
- N) I! y; B. V8 S  m* w
; w4 V3 [2 l2 t4 a        BFS的典中典。

1. from collections import *
   0 j! `* E9 H2 ~+ Z6 w8 U3 s  |
2. n,m = map(int,input().split())3 C% l! r( G$ {8 Y/ q
   
3. mp = [[0]*(m+5)]1 J1 W  O+ W* X( R* g9 _# ]
   
4. for i in range(n):! g9 B1 ~  C0 a5 w! Y4 R' W+ g
   
5.     mp.append([0]+list(map(int,input().split())))
   3 P4 u4 o2 \5 ]' b/ k5 Q7 e* P
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]9 @7 h' R+ }( r3 s\" {  f9 M% B  b
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   ! E; e$ Q  Q/ t9 \
8. def bfs():( W* z: W\" s\" ^8 F
   
9.     q = deque()
   - T6 ^4 O) L  E, I' m- c' w
10.     q.append([1,1,0])
    ' ?# m0 j& l* H% s& z4 B
11.     st[1][1]=17 R1 J% j4 N1 }9 `' r: {. I1 [$ A4 C
    
12.     while q:0 Q4 j$ E  `( U' J) m! d
    
13.         tx,ty,step = q.popleft()( v8 l4 ?) U& C; Q1 F: |  U
    
14.         if tx==n and ty==m:: u# [/ ]6 P$ N5 n( l; m. J: R/ s
    
15.             print(step)
    : \- F\" j/ ~+ a
16.             return8 h- @# X8 e- q! n. C
    
17.         for x_,y_ in dir:
    9 v9 y. |2 L( k4 F; ?2 c
18.             nx,ny = tx+x_,ty+y_
    / l1 q5 X5 F5 I1 l
19.             if nx<1 or nx>n or ny<1 or ny>m:continue; H6 b; Q% J! q\" z$ i+ ^
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue7 {8 P1 d9 M* A4 W, t2 Y
    
21.             q.append( [nx,ny,step+1] )
    9 Q) S% I: R$ e2 {4 Y9 k) L
22.             st[nx][ny]=1, t& X/ V+ K# ]3 M$ Z0 ~
    
23. bfs()

复制代码