python 走迷宫问题

2744557306

题目描述】

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

4 ^  W3 W2 ~. o! G0 |3 c( a# K) {【输入格式】

! e" q# ?( |& Q. l( U2 x  l' m  l        第一行包含两个整数 n 和 m。
# _# d: _  x7 H7 r* q
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

$ T: y1 o( c1 X$ `: w【输出格式】
8 p7 K0 ]: h: x- Q' _9 m
        输出一个整数，表示从左上角移动至右下角的最少移动次数。
' p' ~2 {' M6 x9 N2 [; n
【数据范围】
# c( }9 h# M6 X/ w2 J' H2 R; W: M' Q
        1≤n,m≤100

6 p% g* L3 H+ ?0 ^" @/ j【输入样例】
; ?" k0 \# ^) T: U6 m
5 5
0 1 0 0 0
# Y  h  Z2 s  H% f( p. p& A0 1 0 1 0
0 0 0 0 0
- b: c, w3 Y. g" H# n6 m0 1 1 1 0
  X2 M$ E' Q  ]* i/ Y0 0 0 1 0
" d: W/ I7 Y/ f【输出样例】

8
【解题思路】

        BFS的典中典。

1. from collections import *
   0 ]& ^2 h$ i! e* Q2 C
2. n,m = map(int,input().split())  [7 d) l) `5 L
   
3. mp = [[0]*(m+5)]
   1 T; Y9 `0 u( D/ r0 |
4. for i in range(n):
   ( u1 }1 i  s, m
5.     mp.append([0]+list(map(int,input().split())))6 B, d. ^7 x+ t3 q4 f3 S
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]1 b& h& N3 Q* h  o# W. ~, [9 ^
   
7. st = [[0]*(m+5) for _ in range(n+5)]. C) b& j' A3 P( z3 g
   
8. def bfs():8 t# [, j\" C' t6 R& u( z
   
9.     q = deque()0 E0 o% R, H  z+ y. \
   
10.     q.append([1,1,0])6 K, u6 `6 x  v; s3 S
    
11.     st[1][1]=12 f$ @3 m( q* Y# }+ P1 e& e2 y& c7 O
    
12.     while q:
    & _; A6 P2 m- Y0 A% L
13.         tx,ty,step = q.popleft()* n' u/ o; f# R6 o5 ]
    
14.         if tx==n and ty==m:
    - U( h8 k* V; e* r0 H4 _9 Z# A
15.             print(step)4 u. Q# V2 ]5 t
    
16.             return% A/ @  g7 C  Q- Q% c3 f' l
    
17.         for x_,y_ in dir:
    % P/ W' k/ g- G7 i
18.             nx,ny = tx+x_,ty+y_
    9 e8 V! b/ _& x. L- D; m$ [! ^
19.             if nx<1 or nx>n or ny<1 or ny>m:continue\" X1 m( |) R$ v( _7 u2 q( g
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
      z! v: f+ j6 `& |2 a2 u1 \4 W
21.             q.append( [nx,ny,step+1] )4 {9 u: o3 Y% [4 ?# G1 i- v+ a
    
22.             st[nx][ny]=16 F! ?8 ?5 ?) O: _8 B
    
23. bfs()

复制代码

+ u" G' }8 c8 e8 U; _5 K