python 走迷宫问题

2744557306

题目描述】

4 m3 I. d1 w5 Z7 Q. t        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
2 `! K$ }/ O, {9 p
【输入格式】
4 w3 D0 A/ @. ~0 S: p" O3 I
# Q4 C2 A4 M/ ?( c: v        第一行包含两个整数 n 和 m。

( M' U$ H" K4 _2 y0 f        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

$ g7 x$ D3 I: ^【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】

        1≤n,m≤100

【输入样例】
$ x& ?+ c2 L2 _; ~
5 5
7 G% X3 \. U/ D2 z% R) r0 1 0 0 0
0 1 0 1 0
( r: `/ j& M! H2 \7 Z/ F0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
8 g5 t( p- |: `* A' h5 e
8
7 Y4 C0 H5 h4 O& T3 Y7 d+ U+ a 【解题思路】

/ r* V+ P) u/ T2 E3 M: t        BFS的典中典。

1. from collections import *) U& Y5 z0 e2 c% ^! k( U8 z$ i% x
   
2. n,m = map(int,input().split())
   . `9 J$ b0 ?: U' R& g1 }2 q
3. mp = [[0]*(m+5)]
   7 `% L0 }5 X( R  z  y
4. for i in range(n):\" |) U4 {% B/ J5 i
   
5.     mp.append([0]+list(map(int,input().split())))
   ) h9 b( G6 G\" k3 N* [6 z: ]7 U
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]6 \2 I- V8 s, w
   
7. st = [[0]*(m+5) for _ in range(n+5)]' n3 \7 H) Q% ^\" m+ ~
   
8. def bfs():
   / J! P- J0 S4 `# @5 _: I
9.     q = deque()
   0 j* S/ Q* p. U: U! p6 u& }
10.     q.append([1,1,0])
    , f: j; o3 y- T1 o
11.     st[1][1]=1
    ; ^! U9 z% ~; ]! m, q0 V
12.     while q:; |1 D% ^3 B3 O. T
    
13.         tx,ty,step = q.popleft()
    0 W: n+ H& O$ I$ A, g3 p+ S
14.         if tx==n and ty==m:: |6 Q1 @$ l0 ]; B% y7 _
    
15.             print(step)
    ; N7 _- x9 S2 n, g/ S2 d: X
16.             return
    . F8 N$ \8 ]! R' z( Q1 f1 j4 k/ T! T( q
17.         for x_,y_ in dir:
    : H5 @0 `& g2 v$ W4 c5 O
18.             nx,ny = tx+x_,ty+y_
    $ k0 V7 O2 _3 w6 |( h/ ?$ `$ R# Q
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    # w$ W( o$ |: l
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ! O% o1 C: h6 q* q  z
21.             q.append( [nx,ny,step+1] )  w6 d( z* Z- Y2 ~( c
    
22.             st[nx][ny]=1* Z1 ~& T0 v0 Y8 y* I
    
23. bfs()

复制代码