python 走迷宫问题

2744557306

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

3 S/ p8 f* M4 b8 l+ ]" a  j  W【输入格式】

        第一行包含两个整数 n 和 m。
  P% g/ Y7 X+ s  H  j# a, ]
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
5 C( f0 ?3 K% ]
2 D4 j+ b4 X$ B) [: W【输出格式】
. U/ f9 f+ o4 ~/ @
        输出一个整数，表示从左上角移动至右下角的最少移动次数。
/ _* s+ G5 B- m
9 M/ }7 D' [! a3 z【数据范围】
1 C3 T6 H7 \, ^" U# b! `8 Q
: |7 m* d/ U& [4 {' W        1≤n,m≤100
! ~# e7 l) z0 S0 p2 @, B
2 D7 Z; a% D2 q【输入样例】

' L4 ^6 ?! [9 _: c5 5
0 1 0 0 0
0 1 0 1 0
% \$ B& k' [3 ]; H* l0 0 0 0 0
0 1 1 1 0
9 G, k1 ~% z, \) m* h! F0 0 0 1 0
【输出样例】
) F, B; A/ r2 K  Y8 S/ V7 a& p
  d2 ~6 {+ y8 G$ g8
【解题思路】
& E( D9 W4 K, |$ r
        BFS的典中典。

1. from collections import *. _4 G  g& a/ ~' o. O) s4 X4 n8 g
   
2. n,m = map(int,input().split())# e) V/ U0 r1 d1 `3 N/ Z
   
3. mp = [[0]*(m+5)]
   . y8 }. ~3 n' ~$ K' d9 q% @\" o
4. for i in range(n):
   , b9 ?$ M2 l4 r
5.     mp.append([0]+list(map(int,input().split())))7 y  H. G7 U7 Z  \& t2 M2 \
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   & I2 S! s' Q1 r! {0 ~1 i7 `\" n
7. st = [[0]*(m+5) for _ in range(n+5)]
   \" l* V6 L  l, c, X
8. def bfs():. J6 d5 h8 Y& w, T* _
   
9.     q = deque()
   & ^$ [7 V; u- J3 X# o5 `
10.     q.append([1,1,0])) f3 P9 z! y, v7 i( H5 v; z  C\" `
    
11.     st[1][1]=1* l' {\" ~# d8 ]\" G! \/ |* Y& T
    
12.     while q:
    8 Y# J) s$ ?2 t5 S8 K
13.         tx,ty,step = q.popleft()\" }) F! }( r# Q( U1 @5 Y
    
14.         if tx==n and ty==m:
    # f& i( p9 P3 ]
15.             print(step)
    8 }( m\" L' M# Y! t% q4 d
16.             return. E6 `) T4 _, `' u. N6 @
    
17.         for x_,y_ in dir:+ K  C$ V) V# g' v9 s
    
18.             nx,ny = tx+x_,ty+y_
    0 k! Y9 j8 S9 A, P9 \
19.             if nx<1 or nx>n or ny<1 or ny>m:continue9 P9 W% `  e  s' F8 G- ?  x
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ( n+ p9 `/ N5 ]' s/ c& u
21.             q.append( [nx,ny,step+1] )
    ; `5 m\" w% z& l; I* a
22.             st[nx][ny]=10 `: o) c# k8 w, M* _3 @& J% X
    
23. bfs()

复制代码

. C* v, g( l% k" ?  J/ |+ {/ E