python 走迷宫问题

2744557306

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

【输入格式】

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

- M0 x3 ?( g# T7 }) Q5 o  s        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
7 i) A' l$ g( V7 a5 S/ H- @
# u3 V; O. t, Q. @: w6 I【输出格式】
5 J4 Z& u4 D" W' ?+ L
        输出一个整数，表示从左上角移动至右下角的最少移动次数。
' \' x- W+ }0 C8 _" l
2 P( [# a" X9 W7 s【数据范围】
$ E: B9 C) |" a% M
1 }0 }% }& K. x        1≤n,m≤100

【输入样例】

* o: ~  C' S; h, @/ `9 H5 5
0 1 0 0 0
8 d! h+ z# Q& I+ J  b0 1 0 1 0
5 s! U' e( Z7 w0 0 0 0 0
0 1 1 1 0
6 d, ?, w8 o/ S0 g0 0 0 1 0
; s2 V+ J5 i8 H* U+ W, x【输出样例】

! ?% X6 X9 m2 C. }9 B( q8
9 E2 I* W0 S% h 【解题思路】

  }. e- {9 ]' a1 }; W        BFS的典中典。

1. from collections import *
   , z5 n' v- z/ y4 h  B9 C
2. n,m = map(int,input().split())/ j+ \+ c7 ~# L- `) I7 k, `$ f
   
3. mp = [[0]*(m+5)]! m0 A7 p! a/ y& s: b- b2 K) ~
   
4. for i in range(n):6 J) a, ~; Q\" @  {4 F: _
   
5.     mp.append([0]+list(map(int,input().split())))
   1 |' R9 {' P; V% v+ {; k: T: P6 h
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]6 M1 z* Z. Z, D\" \. o/ D
   
7. st = [[0]*(m+5) for _ in range(n+5)]# g, t% g* \\" r. M  b1 z  x8 t
   
8. def bfs():
     v- R5 |! _2 v1 d/ J
9.     q = deque()0 I# G% L/ R' ?1 q0 B) d: Y; h
   
10.     q.append([1,1,0])+ M3 a3 }3 N! i) k& s
    
11.     st[1][1]=1. o  Z! u9 `( }$ T) U
    
12.     while q:
    0 o) y# ?! q/ |\" d8 g$ c
13.         tx,ty,step = q.popleft()- M/ g8 I, H. C9 y* M
    
14.         if tx==n and ty==m:
    $ j$ G% X. Q( F- y( F
15.             print(step)* a( @2 Z. A4 ^: F2 b1 t# g# p
    
16.             return: h\" D- P. w# k
    
17.         for x_,y_ in dir:* z% c8 c( i. a+ F, O
    
18.             nx,ny = tx+x_,ty+y_7 U! u; ?1 x$ |  h
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue9 S! s3 l: q! p5 S% Z) y' \1 }
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
      J! L) b# N* e1 B
21.             q.append( [nx,ny,step+1] )5 }  P6 f( h- h0 H7 o
    
22.             st[nx][ny]=1
    ; ?' O1 J' i: a3 B
23. bfs()

复制代码