python 走迷宫问题

2744557306

题目描述】
8 s# h- ?# w  [/ o
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
5 G2 c2 t4 l' }1 R1 G
) [* v" L9 r# N* b  X- I! r【输入格式】
# l* W  t( L( h  ?6 P
) S% E1 E+ g% b        第一行包含两个整数 n 和 m。

7 w, h6 s3 v# {) T9 m/ h        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
" R( w5 n/ f* {: G, Q6 x4 d. q
, h$ _+ j% e) ?" C# E【输出格式】
; P1 ?  a' P; \# l9 o- ?) W
% `* t- s, L: D/ J        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

        1≤n,m≤100

【输入样例】

$ G: l6 ?9 h3 t5 5
0 w2 J' [* n3 d7 y' |% w: x0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
, ^$ m2 a' b9 m% e% {0 1 1 1 0
* n- \! k$ v1 j2 ^& |' J0 0 0 1 0
9 V" E7 v8 g+ \1 G/ `【输出样例】
0 B4 o: k/ M; e# @, s8 v
8
+ F0 u4 Q1 d8 U7 C 【解题思路】

5 b0 P$ m+ n6 r) ^        BFS的典中典。

1. from collections import *\" h6 r3 Y( |+ H5 y
   
2. n,m = map(int,input().split())
   8 G) z\" S; E  ^% ~# h$ ?
3. mp = [[0]*(m+5)]) F( @% t! W* V% V& X
   
4. for i in range(n):0 K0 ?$ ^& d0 Q8 }# F9 d; v; c; b5 R
   
5.     mp.append([0]+list(map(int,input().split())))
   . X, J# v5 |- _
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]1 S( \0 d1 v8 L0 q5 Y+ b\" s\" S2 h
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   ) N$ M/ u/ N  T  w
8. def bfs():! t% B% `0 Q9 v* U( Z1 H( S
   
9.     q = deque()
   + i; k3 L) P0 [# a
10.     q.append([1,1,0])
    1 O; v& o- V4 {\" ?+ q2 {
11.     st[1][1]=1
    ( U5 o5 M0 s4 J, ?; }2 |' Z
12.     while q:\" ~0 T* K5 J, O4 R  _# @# Q
    
13.         tx,ty,step = q.popleft()
    8 T\" l, h' [+ f6 c( z5 \
14.         if tx==n and ty==m:6 j% f+ C; v' ?4 y; w
    
15.             print(step)
    2 G% |$ E# r2 k
16.             return
    ( ?; c# U, P) Z- Q) N- k# w4 w& L
17.         for x_,y_ in dir:
    ! x: m3 |: a0 y. D
18.             nx,ny = tx+x_,ty+y_; g$ [7 ^) I! F
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    7 u$ d. l9 ]& n: C
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    % u4 |3 ^; m) b. f0 r
21.             q.append( [nx,ny,step+1] )+ y8 d; \- ?; l5 u( |' a6 l8 g
    
22.             st[nx][ny]=1
    ! b' V# ?: I  V: B
23. bfs()

复制代码