python 走迷宫问题

2744557306

题目描述】

) B' c. s5 W1 T4 l  R$ c) K7 o1 K        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
; z* p$ O9 o: q& Y- a- x
# x. h6 p; ^7 _; h【输入格式】

        第一行包含两个整数 n 和 m。

! O6 @/ ?1 @* [9 Q* I  y8 X' M        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
" `. l5 @, Z  I( t
【输出格式】

# _# S: t8 p0 {( m$ H& r        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

        1≤n,m≤100

4 |# v: _' a8 Y' n8 e. n【输入样例】

5 5
0 1 0 0 0
$ L, F1 j1 x5 U7 f0 1 0 1 0
0 m0 E% \; p' a: j( y7 c2 i, w+ @0 0 0 0 0
: |4 j4 l' Z7 A2 w4 l* l4 r0 1 1 1 0
2 y5 A+ v* N% I0 R0 0 0 1 0
【输出样例】
2 R- O" J2 l3 z9 v* z
. C8 V0 @  A0 w+ z8
$ A6 e& R% L6 Z4 Y 【解题思路】

        BFS的典中典。

1. from collections import *) O\" o& |4 l  ?# w
   
2. n,m = map(int,input().split())$ Z( F6 c( \5 S9 \
   
3. mp = [[0]*(m+5)]
   . B8 v% K5 A9 v/ l% o
4. for i in range(n):
   , j' P/ V5 }  d! G. C! g
5.     mp.append([0]+list(map(int,input().split())))
     z! W/ q9 d: [: U  N
6. dir = [(1,0),(-1,0),(0,1),(0,-1)], Y, \' R- g/ s5 ~. h. U
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   8 S9 D2 E: X% [; ?: y) t0 R6 u9 x  W' d
8. def bfs():/ x+ m  n6 s' D; w1 C
   
9.     q = deque()  f7 ]\" A5 i\" @& C\" j
   
10.     q.append([1,1,0])
    3 ^) R9 [! ^5 X* e( r0 _% t. G; C' X: j! D
11.     st[1][1]=1
    # ?2 @) Z% ^) t  E& v
12.     while q:4 c3 U% w  n* B8 S. o
    
13.         tx,ty,step = q.popleft()
    \" k7 Z8 V) _+ Z\" o) i$ \' ^/ ~2 _
14.         if tx==n and ty==m:
    ! ^5 Q5 L1 d2 g2 F4 c4 X8 i( s1 O
15.             print(step)
    , b$ \9 f4 q: M, D  @+ K5 |2 P3 J
16.             return
    , i  z( _0 N$ L. d0 r
17.         for x_,y_ in dir:/ ?& K2 u; [7 |6 o* t! K
    
18.             nx,ny = tx+x_,ty+y_; I% N1 c4 B1 Z% d4 i. R
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    : e# v9 R& u! m' @
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ; G/ N; u0 l$ e. ]3 {
21.             q.append( [nx,ny,step+1] )7 ~- A0 O* m8 v3 a
    
22.             st[nx][ny]=19 w5 Y7 m* v1 S) o% u
    
23. bfs()

复制代码