python 走迷宫问题

2744557306

题目描述】
0 n2 Z- l, y; \- E  ?! j
8 w( b1 X; B6 ^# k& m4 k        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
/ ?4 e- P. ?: [
【输入格式】
. B9 [8 s" a5 |5 }# z4 C
' B1 c( C, n* e+ o" c; e# f/ w; k3 _        第一行包含两个整数 n 和 m。
+ y; T% L* I2 s- u* y; L
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

  O5 ~/ `- u) C" q( b, h1 e: Y【输出格式】
/ p, T- O: j+ {  M4 M
        输出一个整数，表示从左上角移动至右下角的最少移动次数。

9 c. T" u9 t2 \% _' C' Q【数据范围】

6 [, v* l9 I4 T  i* {: e. ~        1≤n,m≤100
/ Q( r- W) U6 n" N: k
$ }0 Q: C' b. ^3 p% F【输入样例】
# @% A! a) N. ~! i  C# W
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
, e* q- r# V- S0 1 1 1 0
! S) i7 E. N5 K9 i/ m! N& Z0 0 0 1 0
【输出样例】

7 u9 e* N4 z4 S! a8
【解题思路】
% B! ^/ L0 c' x0 ?# c" w5 d7 B
" o( q) i% L) _# x% Y! ?        BFS的典中典。

1. from collections import *' A7 E. d; w\" \$ q# Z
   
2. n,m = map(int,input().split())
   % b9 a3 s$ n; @: q- W; {
3. mp = [[0]*(m+5)]
   . E4 p4 z- X- ^  c) \4 [# |
4. for i in range(n):\" O! l6 d! o1 Q; }' X7 O5 x6 H. O2 @
   
5.     mp.append([0]+list(map(int,input().split())))
   \" x\" E% D# C8 |5 F
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   / T  h4 c: Y% O- Y* h) `2 t4 y- L
7. st = [[0]*(m+5) for _ in range(n+5)]
   / F\" U# C: o2 Q8 F
8. def bfs():* @3 m$ i, G1 a. }
   
9.     q = deque()1 k' ]# F2 A4 `2 P
   
10.     q.append([1,1,0])0 ^/ P1 ~& E2 X
    
11.     st[1][1]=1+ |$ y# Y0 G\" p, u+ M9 F) B
    
12.     while q:
    % f# Y/ Y( Z& C8 N3 E7 e
13.         tx,ty,step = q.popleft(); _- z3 U7 l) e, _) t
    
14.         if tx==n and ty==m:
    6 d* g- D# s8 d\" b9 q2 w/ I, X
15.             print(step). L\" V0 p7 s' K( ~/ U+ |+ y0 U
    
16.             return
    9 G# y6 r' A* A9 t) g. E- M% M0 P  J
17.         for x_,y_ in dir:
    * p8 K\" {& P# ~' Y! x* |- l. j! a
18.             nx,ny = tx+x_,ty+y_
    \" ^' E- r7 f  z+ b) X6 q0 M3 T& y+ B
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    $ ^4 q: J4 s$ `/ X\" _* i, x
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    \" m1 P7 O3 n0 W# f. z2 L0 B
21.             q.append( [nx,ny,step+1] )' ?  n- L) _! _0 V
    
22.             st[nx][ny]=1
    & h9 o0 |( _9 p2 N4 d5 t
23. bfs()

复制代码

/ p& [# H+ W) H& t