python 走迷宫问题

2744557306

题目描述】

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

【输入格式】
- L2 d) e) Y$ E0 t& n3 q* H
        第一行包含两个整数 n 和 m。

        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

+ v9 [2 [2 J9 ~* ^3 ~【输出格式】

# @) i, f& K8 {. K        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】
. z) q! S9 K3 k. \; {0 ]$ R6 \
. `7 T( u$ s% v        1≤n,m≤100
7 Q4 i! [  p5 m  n0 b2 T0 r; o$ _' `3 e
- C( T0 H+ n. @* {: v/ _* C  K【输入样例】
8 N; K+ C. a' `6 c- M
5 5
2 t( g7 P2 U  b; k& u7 ]0 1 0 0 0
0 1 0 1 0
5 ]- i7 D' [) n- Y0 0 0 0 0
1 I: H$ g/ _7 f* E) ?0 1 1 1 0
0 m2 ]& _( h; S5 w5 }1 O0 0 0 1 0
8 e! X' o& W1 p' r4 S【输出样例】
2 F0 ?% ]- J) \/ z3 }% |. @/ R/ Y
8
【解题思路】

        BFS的典中典。

1. from collections import *4 P/ w9 e! ]. @
   
2. n,m = map(int,input().split()). c) e% O* v1 J0 R
   
3. mp = [[0]*(m+5)]
   1 G  r. Q% _6 L& F) c. I. R/ K
4. for i in range(n):) v* ]2 M, F2 R+ G\" K5 Q
   
5.     mp.append([0]+list(map(int,input().split())))
   % P2 Q* c/ K& z* O
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]9 {0 [% ]- C1 ~+ I/ S1 o
   
7. st = [[0]*(m+5) for _ in range(n+5)]6 h* ?1 Z+ }' e3 w5 V' \\" P
   
8. def bfs():
   & _/ c8 H: N% P% y4 y7 R
9.     q = deque()! e3 \2 Q5 D4 }  x. ~9 f
   
10.     q.append([1,1,0])
    + Y\" {0 s9 m$ n6 I' f# g
11.     st[1][1]=1  P8 ~5 R  j* m\" Q3 K& R
    
12.     while q:
    * v2 ~  K) v\" R. ^: g* Y
13.         tx,ty,step = q.popleft()
    - H5 D, P9 ~3 b& U1 G( ?* R
14.         if tx==n and ty==m:
    / G' a2 a6 L4 O. x
15.             print(step)
    9 l$ g. L9 Z! L# `$ t# @
16.             return! M* v1 U6 d4 v- b7 k& a
    
17.         for x_,y_ in dir:( g( W% I9 l, @, I$ L6 O9 a5 s
    
18.             nx,ny = tx+x_,ty+y_
    # p6 E! l. z2 g- l, }- O1 E& g+ S
19.             if nx<1 or nx>n or ny<1 or ny>m:continue: p# ?& v9 r6 E% Y\" Q0 [
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    9 j6 l; @  u; V* Z; P
21.             q.append( [nx,ny,step+1] )
    9 @3 W' y6 D' s\" t$ s3 D6 x
22.             st[nx][ny]=1
    , w% U1 @2 }/ w) T
23. bfs()

复制代码