python 走迷宫问题

2744557306

题目描述】

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

  v0 k5 U/ g9 u1 P+ ^; B【输入格式】
) e# s$ H) e9 L2 p  g4 H
; [' g! a" f! A; @% m) z; y  q7 k        第一行包含两个整数 n 和 m。
& b9 W- g) {1 l6 `$ J6 ?
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

  t4 V6 K  T4 U, q【输出格式】
- [( m1 z9 W0 w( w
. f' T: j. H0 _0 E        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

) b' W$ t# C! d* K  y        1≤n,m≤100
6 ]: ^( f5 g# w& V& {" v( |' d/ F
2 {+ b% A% l( _4 ~! |) o4 s【输入样例】

) {4 E2 z% H9 A5 5
0 1 0 0 0
0 1 0 1 0
8 F) O4 D3 W1 `0 j/ a) E+ n0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
1 J+ b8 u1 t( J( O  c" F# v% H【输出样例】

8
) q" |8 |/ V- g9 `: M6 E# | 【解题思路】

. {) \: P3 {' k2 O- @3 {        BFS的典中典。

1. from collections import *
   1 |/ O6 P% x) _( {
2. n,m = map(int,input().split())0 W\" _  s4 o* K: F  L9 n\" I8 E
   
3. mp = [[0]*(m+5)]  A! ~: r8 [7 l7 B
   
4. for i in range(n):
   2 e& {$ ]* |# b  y% n
5.     mp.append([0]+list(map(int,input().split())))* M, Y0 s. A0 G. ?8 D% M' W  v
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]+ V\" d$ l; j8 L+ \; o  r
   
7. st = [[0]*(m+5) for _ in range(n+5)]; g2 Z8 d8 {* G4 W& ~
   
8. def bfs():0 n, F2 k/ H* S  d5 X  U1 Y8 W. O5 }
   
9.     q = deque()
   : m* D! t\" @2 W* L) p% Q5 l. k% P
10.     q.append([1,1,0])
    1 j1 p8 b' e0 {/ M% ^4 s' D, J
11.     st[1][1]=1
    . `\" f9 ~) O7 s\" U- U: r# [  ?
12.     while q:
    / `& B0 u  {2 u& r& h* D+ E
13.         tx,ty,step = q.popleft()3 R\" l$ z) n7 c\" g8 m8 d, B5 ~
    
14.         if tx==n and ty==m:
    # Z! k; T0 h, q- B+ H
15.             print(step)7 @' x; G& w7 B( L) W+ l
    
16.             return
    / t\" I, _% p5 J
17.         for x_,y_ in dir:0 e' w2 j( ~* h' N
    
18.             nx,ny = tx+x_,ty+y_
    * O7 r0 _% E9 \* A+ c2 b
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    % o$ o4 S: z4 Q) r' G! N7 ?
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    * k$ J# c/ j+ V$ x' ]7 S. |& h
21.             q.append( [nx,ny,step+1] )+ M6 o- C2 E8 d; C\" y- Y/ x, I
    
22.             st[nx][ny]=1
    ( C6 N! X. F\" h& e) b# k8 N
23. bfs()

复制代码