python 走迷宫问题

2744557306

题目描述】
+ d. g$ [; P4 B- _/ F
3 L. X  p' f( r9 m7 h+ u        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
8 F( j, Z/ j- n( U7 d. H; F9 M
3 w7 M- B' R( O! i$ M+ j【输入格式】

        第一行包含两个整数 n 和 m。
- F! c3 _2 c/ ~
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
$ J( v2 L5 [9 ^$ M6 B% Y
8 e0 I' [1 Q% g. Z; V【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
; |' p5 \2 J4 K; S/ w' i$ n! D
2 X: Y8 A) N$ J: q( C) c【数据范围】

4 M9 W1 t, T8 K' U) f1 E        1≤n,m≤100

【输入样例】

% a$ O  }- s: n$ O1 ~$ _5 j- f5 5
0 1 0 0 0
0 1 0 1 0
/ H+ R2 g. f' _" `; I7 h+ d0 0 0 0 0
  Q. i- d: R. ?! R1 C7 b$ K! T0 1 1 1 0
0 0 0 1 0
& v1 a* {5 Y1 G【输出样例】
9 b+ o. ]9 T+ l& S/ d1 {
8
【解题思路】
6 K, l* U: U4 ]) C
        BFS的典中典。

1. from collections import *
   0 b5 i) c$ q. U7 ~
2. n,m = map(int,input().split())3 A% L) }9 k: e* Y: V
   
3. mp = [[0]*(m+5)]$ h9 D7 `, g1 X) N& C& x
   
4. for i in range(n):
   ) v9 `9 Q* L0 A- w& ^/ F2 t
5.     mp.append([0]+list(map(int,input().split())))
   ( Z$ \: i/ z& I: `4 r% e
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]\" G8 e: e( k3 ?9 G
   
7. st = [[0]*(m+5) for _ in range(n+5)]! F2 y; e3 ~* t# [2 d. {
   
8. def bfs():$ p3 w0 d, U) @7 Y2 l
   
9.     q = deque()1 _% g0 b5 v\" n# |' `; P
   
10.     q.append([1,1,0])
    0 t, {( h  o, s' @6 n2 |
11.     st[1][1]=1
    # o, x2 ]3 m: C  Q2 T$ I! R8 o9 y\" O
12.     while q:
    9 ?! G% v$ F$ X2 }9 p& W
13.         tx,ty,step = q.popleft()
    2 |( r# V( S2 X9 _. `' m
14.         if tx==n and ty==m:
    9 c( A) U$ J( w3 Q! f( R
15.             print(step)
    / X4 u. w: J2 v/ t; d: x: a
16.             return
    ) L( ?! D& g/ f, ?\" U
17.         for x_,y_ in dir:
    ) \4 M& P* U4 R\" L& w
18.             nx,ny = tx+x_,ty+y_
    6 a. K5 V3 h% {8 p* E
19.             if nx<1 or nx>n or ny<1 or ny>m:continue0 N5 L8 N# w) f& }\" \# [
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue$ ]- l( G% ]: \2 i3 D6 c
    
21.             q.append( [nx,ny,step+1] )! x/ \. c: t: O4 a5 D' K
    
22.             st[nx][ny]=17 b8 g) m) F# ~
    
23. bfs()

复制代码