python 走迷宫问题

2744557306

题目描述】

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

【输入格式】

        第一行包含两个整数 n 和 m。
9 R7 f- K; c- L, J- D
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
' b# C1 E& q/ ~( I; o4 m1 x
【输出格式】
, J; }1 u2 d) Q1 Z/ P, V
9 N0 s5 D! m( ^2 Y  i        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

        1≤n,m≤100
- d! `+ J9 @6 @% ~
0 S) m! \/ [) X; |) j1 k% e【输入样例】
9 F* p: U, Q7 I0 f
! [0 k+ x2 H! i1 h5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
- j. b% ^0 \0 ]* r# p0 0 0 1 0
【输出样例】

3 S! s6 I  Y6 `8
【解题思路】

% o2 W5 \; x3 L' p) \2 F) F        BFS的典中典。

1. from collections import *\" K\" R1 S- n' X3 x) `) {0 T
   
2. n,m = map(int,input().split())' l7 W- t+ h2 v7 @% |0 R9 M! w3 u
   
3. mp = [[0]*(m+5)]
   9 R# E/ ~- k: G# B+ K- H* X
4. for i in range(n):2 y& l% g$ M. t4 U$ q; V
   
5.     mp.append([0]+list(map(int,input().split())))% q5 }, R# F\" _; n
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   8 O4 Y$ L, v2 {2 u2 ~. ^\" c
7. st = [[0]*(m+5) for _ in range(n+5)]
   5 J* K- k  Q, }3 n. v
8. def bfs():
   $ H- B( G% u5 Q, a
9.     q = deque()
   1 Z5 l( k9 |! J. {: ?* u( {; T
10.     q.append([1,1,0])
    / {- p& H! j6 e, e1 j8 R
11.     st[1][1]=1
    0 m  Q( u; ^) a& c3 c
12.     while q:
    - A\" @- Q6 E6 Q\" l
13.         tx,ty,step = q.popleft()
    0 q5 Y/ `! s8 g9 M# l  x; q
14.         if tx==n and ty==m:3 f$ I0 P. e: K9 y3 u! J+ z
    
15.             print(step)
    * y; r6 v3 j/ I: m; {3 a
16.             return- R% q+ K$ B9 Y! ^
    
17.         for x_,y_ in dir:
    : Y: ]5 ]- A! |  M) Y\" |4 }
18.             nx,ny = tx+x_,ty+y_
    % J9 W7 V& Z\" a7 q% c  t% j
19.             if nx<1 or nx>n or ny<1 or ny>m:continue3 j* P: e% K3 D9 Z3 E& _\" }
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue  b1 _( n( d6 Y$ t! I3 b, a
    
21.             q.append( [nx,ny,step+1] )
    4 a/ H) P/ X* z! S% L% k
22.             st[nx][ny]=1
    9 f2 Q5 V7 `5 f8 e' q
23. bfs()

复制代码

! H! ^" T4 `$ D0 G0 B7 h. k