python 走迷宫问题

2744557306

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

0 ~+ d3 a9 r* L. m; s+ H【输入格式】

* b5 f1 N4 i" ^4 X4 R        第一行包含两个整数 n 和 m。
0 E1 Z" m, a& _& d1 h: U1 w
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
# C, f. r6 Z' C
, m0 t0 ]$ S+ x6 U& v( y【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
0 r2 v/ i# E$ J9 S- n
【数据范围】
8 x& o, ~+ m2 z+ X- x
$ N" X+ {5 v' L/ v        1≤n,m≤100
2 w' J, J% ~1 i, G0 `
0 _4 u, a# G' k& T; R& G【输入样例】

4 Y! m4 A$ k. d/ J; x5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
6 I! a4 V; N- J" B
. Y5 s. x& M5 p2 Y8 F) ^( B: Y8
5 t$ J  w2 s& Z, }/ K+ W 【解题思路】

        BFS的典中典。

1. from collections import ** _1 ^( U8 _5 p) v) W+ Z% L
   
2. n,m = map(int,input().split())3 I9 V/ [\" @# k2 r) [
   
3. mp = [[0]*(m+5)]
   / j2 z' m' g6 C\" ]' Z  p( o
4. for i in range(n):
   ) d# @, I! l0 n
5.     mp.append([0]+list(map(int,input().split())))\" c! ]% g9 G! |, }7 Z
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]: f& n/ p8 E: s1 y* k2 ]3 l
   
7. st = [[0]*(m+5) for _ in range(n+5)]& q7 v5 r8 Y( A
   
8. def bfs():( }$ E+ }! y5 m3 X% g
   
9.     q = deque(); ]: H+ u3 Q7 ^1 O  E
   
10.     q.append([1,1,0])
    ' u# n2 Z  _, I! `9 m! b
11.     st[1][1]=1
    \" |) D  m; u0 k\" H, W0 `
12.     while q:
    ; |& W1 o/ C# y  y
13.         tx,ty,step = q.popleft()& r* z5 w) u% J* w3 ^' b& O
    
14.         if tx==n and ty==m:
    . B8 q: U% {4 Z2 c! v) e( p, Z) S
15.             print(step)
    7 L& D) I6 d\" ^8 i$ g7 f2 F0 \+ |
16.             return# b\" C. M+ j7 W5 B' b$ H
    
17.         for x_,y_ in dir:
    ; a; b8 O0 O+ w$ o0 B( o- a
18.             nx,ny = tx+x_,ty+y_0 B. ?& q$ P. p/ F
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    ; v' f* ?& C6 [
20.             if mp[nx][ny]==1 or st[nx][ny]:continue! n4 J, E+ q& \, w0 m; C6 y3 A. m8 {
    
21.             q.append( [nx,ny,step+1] )
    4 O0 W  ~' @: i* k5 Q1 b
22.             st[nx][ny]=1$ p; r: x2 ~( T3 M
    
23. bfs()

复制代码