python 走迷宫问题

2744557306

题目描述】
: g5 X6 L" B) g: t; t: |/ A9 Z
$ e- g0 q+ F& T2 \1 @( {; }        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
$ r1 Y% p+ K5 s% P6 G+ _- Q
【输入格式】
4 R2 N' b9 @- h, P/ \& ^4 }5 H
" K) P7 ^3 y+ p, V; Z        第一行包含两个整数 n 和 m。

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

【输出格式】
. `4 k9 ~) ]0 g5 W
7 I  Y& G3 D0 d' u        输出一个整数，表示从左上角移动至右下角的最少移动次数。
3 \1 C% E& [0 w( R3 x( ^$ V0 W5 X
【数据范围】

        1≤n,m≤100

& H0 V4 N" \$ X$ \$ ?, t6 E9 e【输入样例】

* e% d# @3 n- ?5 5
: j/ N6 h' r# S  _; P: q0 1 0 0 0
3 `/ E! C2 J0 s) }7 D/ O0 1 0 1 0
. P. Z5 m# l- ]% T6 A0 0 0 0 0
6 x4 q) @- X8 l" p( W7 q- f5 J0 1 1 1 0
0 0 0 1 0
1 `3 P7 P8 ?( e【输出样例】
% M' c+ v/ M; m0 S* ]# N. R% X1 U- e
8 ?! T% y( p! B2 O( {( s8
) V8 `6 k: c: h" \' J, X6 _ 【解题思路】
" o% U2 g7 o7 U3 W8 T6 Y* z
1 q3 d( `, g& Z& r. e        BFS的典中典。

1. from collections import *
   6 W2 T& V! P2 I  _0 ~+ C
2. n,m = map(int,input().split())
   # n+ f/ R! i6 n* ~2 \
3. mp = [[0]*(m+5)]2 f! p$ h: V9 t  W\" [0 m
   
4. for i in range(n):
   5 i: K# e6 U1 B! z, g, Z  ~
5.     mp.append([0]+list(map(int,input().split())))# i  O. \, d& T
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]) O. O% }; k4 s, h1 e5 J, m
   
7. st = [[0]*(m+5) for _ in range(n+5)]. S) ~0 C: P/ B6 M1 ~0 w5 C
   
8. def bfs():
   & W9 H0 O, S. @0 z  h; @
9.     q = deque()
   2 ^; d$ x& F: B2 K6 G
10.     q.append([1,1,0]). `4 i2 ~. z  |/ f) W: ]
    
11.     st[1][1]=1
    ) |% O. X: E4 n+ {
12.     while q:7 [# ?- ^- V/ E) l3 f
    
13.         tx,ty,step = q.popleft()
    0 G0 K& U+ Z8 A3 R3 y' ^7 ~. E
14.         if tx==n and ty==m:- i/ w6 J+ j# N: d3 X0 |8 [& ?
    
15.             print(step)
    ; t3 W: X, _: I
16.             return4 L& k3 u( n( x3 A6 e. @
    
17.         for x_,y_ in dir:
    ; w; l' l) Y4 \6 i4 b
18.             nx,ny = tx+x_,ty+y_
    6 y, }; h/ F: G( i3 A
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    ! a' s\" m8 _# ^  n6 `
20.             if mp[nx][ny]==1 or st[nx][ny]:continue: P/ k; x: b5 W  \, R
    
21.             q.append( [nx,ny,step+1] )) }0 m/ s1 ?, z& M8 K7 V; E2 _
    
22.             st[nx][ny]=1
    9 A1 G0 u8 A\" s8 @
23. bfs()

复制代码

7 ?2 O/ q- U. L" O