python 走迷宫问题

2744557306

题目描述】
: {, {. ~% e: R6 D# s/ @# i6 K+ w
& D2 P. r( M6 u  r) Q        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
! y, |, P, n2 L3 U3 r
【输入格式】

        第一行包含两个整数 n 和 m。
: U% M+ A( w  i
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
& N& a; l1 Q0 Q3 T
【输出格式】
3 R" p( v( F5 L+ m5 B: k
4 h' i* d9 s1 u! L+ ?7 d4 O3 C4 l        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

  n8 Q3 v2 R. e' K0 V8 d! _        1≤n,m≤100
: a5 V* [' M" w3 _" ^; k) E
8 |! Y. p" S9 A" l1 p# o( T: A【输入样例】
/ T: \1 |- q3 k
3 I7 S' T( w. ?# ^7 Z5 5
% h: {" w( r8 B0 1 0 0 0
; P: n# K0 f+ y% Q# i0 }0 1 0 1 0
: [7 E9 I6 K. z( y' b2 c. d# v7 e0 0 0 0 0
8 z5 X& H, R9 {0 1 1 1 0
: R8 u5 T4 z/ A2 p( r- K0 0 0 1 0
7 y( a$ K% D. v; y  O8 B' T8 ]【输出样例】

8
, T. l% J4 k: h# A# V 【解题思路】
' b, L) E% L5 X* v0 O
) Z: x) t( D  w& e        BFS的典中典。

1. from collections import *' a) L/ V8 g3 T7 F5 R\" b. k
   
2. n,m = map(int,input().split())8 |0 d& j) D& d2 O1 X
   
3. mp = [[0]*(m+5)]% E9 m$ t\" G4 b+ ^\" F1 _' M0 L
   
4. for i in range(n):: W2 d8 _! {\" O0 Y$ ]' ^2 ^
   
5.     mp.append([0]+list(map(int,input().split())))( g( e. L5 @+ I/ l1 S- @) e# K) F
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   4 _4 J) W/ Q; l0 g6 R1 v5 o5 M
7. st = [[0]*(m+5) for _ in range(n+5)]
   ) L1 ~5 x9 u0 m6 Q* l0 B6 W
8. def bfs():
   0 d) U3 A; U4 U1 q9 ^8 s0 R0 B
9.     q = deque()
   1 ?0 r* v$ K) F2 b5 Q, G
10.     q.append([1,1,0])5 Z! b# [, V7 d8 s5 [+ X1 v* J& Z4 M1 `
    
11.     st[1][1]=1\" v3 a\" v8 i1 V\" ^: W  T
    
12.     while q:
    9 |& C/ [( q5 g& f) ^$ z' `$ b
13.         tx,ty,step = q.popleft(); M4 c+ D) [0 E8 i
    
14.         if tx==n and ty==m:
    2 t9 ~, X7 ~! Z: \
15.             print(step); t8 w: C% F: e/ H/ |
    
16.             return7 r2 f8 R' G! N
    
17.         for x_,y_ in dir:
    8 S6 E' b\" y$ d( z# ?& z8 O- k
18.             nx,ny = tx+x_,ty+y_4 D* x4 r6 t3 p* C. F4 B$ G
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue1 b) `0 s8 O\" Q: I0 s% e$ P5 i
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue7 X\" ]' d$ @& X2 C; {+ _$ c
    
21.             q.append( [nx,ny,step+1] )( X( B6 S\" a. M/ P
    
22.             st[nx][ny]=1
    7 P8 s* e\" W: S! x
23. bfs()

复制代码