python 走迷宫问题

2744557306

题目描述】
) o( H4 t! ~1 e+ W. V
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
8 W) {$ Z6 ?3 U+ ^* u
【输入格式】
0 k  Z3 P  g% ^( _% h  G9 y
+ V1 F1 W! C: e* X        第一行包含两个整数 n 和 m。

  U0 E  A$ z4 d/ Y  O- I        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

% A1 q; q( C$ {' S3 J3 \+ J【输出格式】

6 {' ?) }: d" c. C1 g1 ]% U        输出一个整数，表示从左上角移动至右下角的最少移动次数。
+ ^" {  e  p7 v' O( D( q6 t, p
* k/ }& ^% t- W! V7 `! o4 ~/ }3 q【数据范围】

        1≤n,m≤100
8 n; N" W% i8 x; ~7 K  l
# {8 F1 T" a, X0 k/ s# [$ R  q" e6 x- j【输入样例】
4 D) S7 ~/ L- ^9 i: t( e2 X
7 z5 A9 [7 \' o2 w( B/ j5 5
4 x* a7 s- R7 A0 l5 n0 1 0 0 0
1 g; l& @: n8 N/ _0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】

8
( ^* C7 t7 t8 m/ f 【解题思路】
3 a- o' |( n5 u9 R) P9 \+ f5 \
* Y3 y  |  l2 S        BFS的典中典。

1. from collections import *+ a: O1 @\" M' `5 c+ M
   
2. n,m = map(int,input().split())
   5 n  g4 E# [9 b, t2 T+ b# G
3. mp = [[0]*(m+5)]
   9 y* @# t) A8 e: }3 s
4. for i in range(n):
   ; s8 D; s& Y9 R
5.     mp.append([0]+list(map(int,input().split())))
   ( p- S1 f. ?\" V3 Q) d2 r3 k2 K
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]2 z7 l5 G* R+ @
   
7. st = [[0]*(m+5) for _ in range(n+5)]' K8 N7 p# H/ @
   
8. def bfs():7 u\" H# T& o) R0 V
   
9.     q = deque(). o7 P9 }3 r/ V7 ^. v; Y  L: y
   
10.     q.append([1,1,0])
    5 D/ ^5 _2 _- r
11.     st[1][1]=1
    + I8 G/ q5 f. P+ k& }
12.     while q:
    ( }4 w# r- M1 L6 l4 R
13.         tx,ty,step = q.popleft()% w4 O9 _+ ~  W; O; j6 ^) n
    
14.         if tx==n and ty==m:
    + _/ D) m% O9 w2 S/ d; Z6 J' B4 T
15.             print(step)
    * z5 n* k. E: X5 G
16.             return
    , Y. Y+ p4 N. C3 a
17.         for x_,y_ in dir:
    , K2 @+ Y: s; S: x8 i& E
18.             nx,ny = tx+x_,ty+y_/ g% c# ~$ k- d+ z\" H
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue6 z9 V2 t6 f6 Q6 O
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue* s/ L' k* A0 U0 B. A7 B5 y% C8 U
    
21.             q.append( [nx,ny,step+1] )# y3 H& H: ?6 ~+ x7 M( Z# `' p9 G6 R
    
22.             st[nx][ny]=1  d3 Z& m2 d- G2 {- N
    
23. bfs()

复制代码

# e' B4 D( k: @; F3 M& M- m+ r5 [