python 走迷宫问题

2744557306

题目描述】
9 C7 V  }' J0 n" ~( s+ Z3 U5 s
$ T; o: p5 O3 v0 T        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
" x. ^+ o: W. t' H! q3 C0 ?  m
2 r: }" `5 `% P9 m【输入格式】

) y( |( ]  f/ {$ v& k; a/ \        第一行包含两个整数 n 和 m。
3 e$ k! o$ e( X
; z- l" p, z2 ~4 r" j! l* W        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
; N3 m1 c. d% k! z& e
【输出格式】

, L; P# Q4 Z, }# Z4 x6 G7 T2 p+ E        输出一个整数，表示从左上角移动至右下角的最少移动次数。
, Q; l$ D- {& @! B" n6 b
$ w0 Q" G  B! Y【数据范围】

  _& N+ g+ r5 b' [- Q: j/ V- Z        1≤n,m≤100
* [  ]" w3 ?; H8 a5 j8 n" H8 i
; Y5 ]0 i5 }  D5 ]% `【输入样例】
! N& e0 }2 P2 S) _: I; G. p, d1 H
% f  O) x4 a; x7 w5 5
0 1 0 0 0
- H: E- {  U" P+ a$ O! U: s  p* S0 1 0 1 0
0 0 0 0 0
8 I; O3 ^, F" B' Y0 1 1 1 0
0 0 0 1 0
【输出样例】
/ d9 q; o; }" V$ G+ [2 s
7 U. z6 ~6 @+ [- [1 w% t1 P0 O* R8
4 D" N3 `9 r9 g: y' R  ]6 q9 w 【解题思路】

        BFS的典中典。

1. from collections import *! W' ^. ^- g0 Q- V9 D) b
   
2. n,m = map(int,input().split())0 b6 }. E3 @- }* _# \' W
   
3. mp = [[0]*(m+5)]
   6 {: S& i9 M) v0 Y9 E
4. for i in range(n):
   ' _4 P- j  @) G* M8 U# ]* X
5.     mp.append([0]+list(map(int,input().split())))\" m! Y$ w: N9 p: _# Q( X
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]' T* O3 Q0 y% D6 j5 K( o) E
   
7. st = [[0]*(m+5) for _ in range(n+5)]% I4 c! p% w% J2 G8 v9 u
   
8. def bfs():! U/ S6 j- d9 V' ?3 Y
   
9.     q = deque()
   \" [& G' A! H' q
10.     q.append([1,1,0])$ ^& a/ h% \; {* l. _
    
11.     st[1][1]=1
    8 ~! ~0 l  {7 u6 E
12.     while q:
    - z/ f1 @* K# T4 y; h3 Y
13.         tx,ty,step = q.popleft()
      U0 m+ |: P3 ]- K  H5 R
14.         if tx==n and ty==m:2 T. M% j) `, G3 k( c\" X
    
15.             print(step)% k* k- L1 D, k
    
16.             return
    / M2 T& _  ~: g; W. W% ]
17.         for x_,y_ in dir:
    # r7 _7 A# b! N8 E! e
18.             nx,ny = tx+x_,ty+y_
    # k5 ]7 _% b8 q1 S
19.             if nx<1 or nx>n or ny<1 or ny>m:continue4 Z* ]0 m3 c6 N, ~
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue. M1 p' _- J+ u3 b/ U
    
21.             q.append( [nx,ny,step+1] )
    ) `6 c: y* S- L' T
22.             st[nx][ny]=15 q6 m' k: Y$ T/ j& H
    
23. bfs()

复制代码

: H- s8 H% |! V. L( O; k2 i3 V