python 走迷宫问题

2744557306

题目描述】

        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

【输入格式】

        第一行包含两个整数 n 和 m。

        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
8 x% s2 n2 K+ ]' W3 s+ B
【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
* b# A5 \/ K  V# {% J
【数据范围】
/ Y/ D, v" S) E& S) A- E* C
* Q, j; }0 m# G, `* G+ B        1≤n,m≤100

【输入样例】
4 x! K! N- U6 B# k6 O
5 5
5 H+ Y2 `$ T- Z0 o. {0 1 0 0 0
  x2 R9 ]2 [* t9 c5 e0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
; A+ A( f" z4 }0 u# R5 M, S# |: Z【输出样例】
; \$ g. r) z) x! F1 ?: z
8
【解题思路】
" [/ ?( U# O& A" T# Q; ~7 }3 m
" C: ]/ l0 w8 }  U# T5 u# Q: n        BFS的典中典。

1. from collections import *
   , i# P& K. ^, x7 z# T7 e
2. n,m = map(int,input().split()). w: \- z, B: m0 S! c
   
3. mp = [[0]*(m+5)]+ r! Y( O( [& @% X: L1 S\" ]1 R/ O
   
4. for i in range(n):/ S\" Q( e& s0 m; c2 P0 s
   
5.     mp.append([0]+list(map(int,input().split())))( {. z. B- W) |+ G1 I+ s# J
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]! A) h) ^7 R. O
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   1 K  A8 C. q; o( d; W8 N
8. def bfs():& O6 X) Z( v! I8 j3 _, R$ [\" o9 o
   
9.     q = deque()
   - Q( H6 g3 N! M8 K7 [
10.     q.append([1,1,0])\" t9 Q# p8 X0 {1 u5 g- N$ H% V
    
11.     st[1][1]=12 ^  D. ]- W1 O  a/ I6 @
    
12.     while q:- E2 Q# k9 U, n7 r9 a
    
13.         tx,ty,step = q.popleft(). G# a4 b\" J& W. m\" w) U7 B  w
    
14.         if tx==n and ty==m:\" I6 ?) ], m& X# Y6 B* ?
    
15.             print(step), Y4 ?% u# N8 J+ z: `5 y
    
16.             return8 T; e\" Y) {  R+ X, c
    
17.         for x_,y_ in dir:
    * |! e/ @9 I) l* @4 F5 U
18.             nx,ny = tx+x_,ty+y_8 m# R: _0 b% _\" y3 {
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue6 H  b8 p8 ]' E* p* @* |7 V
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    9 w: X! z+ _4 x4 O1 P
21.             q.append( [nx,ny,step+1] )
    + t' Y& a  H4 \  ~+ a
22.             st[nx][ny]=1
    : m6 X$ J\" N\" q- z
23. bfs()

复制代码

, {* U. ?/ T2 j0 I  U5 c