python 走迷宫问题

2744557306

题目描述】

        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

【输入格式】
3 n. s( F& o+ T1 o9 I) f
% L* P7 q; P2 \        第一行包含两个整数 n 和 m。

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

2 \  G. O0 E6 a3 e* S  V+ P【输出格式】

3 p) B8 }% Z/ e' C. n- t% A. t) k) m        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

        1≤n,m≤100

& B* c5 k( M; W; C9 d【输入样例】

5 5
0 1 0 0 0
% {) F4 P+ r; i. q* d0 1 0 1 0
0 0 0 0 0
& I' x$ q; l9 t5 B  l0 1 1 1 0
" [& ?5 y( [6 k  y% W- W1 T0 0 0 1 0
【输出样例】
+ F6 c9 d- h9 Y9 T8 n
8
【解题思路】
9 M" E! O0 a9 L5 R  c
        BFS的典中典。

1. from collections import *
   / t- c- G) M\" B* t! s: E
2. n,m = map(int,input().split())2 n/ M% ]6 v$ H; u
   
3. mp = [[0]*(m+5)]# V. z* \( b, ?9 a$ v9 o
   
4. for i in range(n):
   1 R% e& ~1 W6 H: n
5.     mp.append([0]+list(map(int,input().split())))9 a; i\" S. {% V9 V
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   ! J2 Q. o6 Q2 P5 @# f/ B+ x
7. st = [[0]*(m+5) for _ in range(n+5)]0 S4 G$ Z  {% T8 M# d
   
8. def bfs():
   & @) U  s! j) a# r5 |2 t7 ^
9.     q = deque()
   ! v% n9 E- T. Y! d0 {2 {$ g
10.     q.append([1,1,0])
    # C2 _. K8 f$ T. R# S' \7 W+ i
11.     st[1][1]=1
    4 v6 c% L/ [$ L\" d& s/ {
12.     while q:
    4 g1 F/ F) i: B' Z7 ^! t0 S
13.         tx,ty,step = q.popleft()% ?0 d0 o8 u6 f. L
    
14.         if tx==n and ty==m:2 {1 v' E3 N; v) K) x9 Y3 }
    
15.             print(step)
    ' }2 ]/ Y& {- f) o' \& D
16.             return! }8 m; m8 K7 |$ }5 R# |3 U
    
17.         for x_,y_ in dir:
    3 {% y9 l+ u! t
18.             nx,ny = tx+x_,ty+y_0 n3 L6 W! A' H$ E' k
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    7 p1 z% Y0 a& E$ Y2 i+ a* E) T
20.             if mp[nx][ny]==1 or st[nx][ny]:continue. a. o, B4 U4 h0 w- s+ Z: X& l
    
21.             q.append( [nx,ny,step+1] )5 _# q. ~8 w) G
    
22.             st[nx][ny]=19 j. n' v. i' l% g& g
    
23. bfs()

复制代码