python 走迷宫问题

2744557306

题目描述】

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

) q: ]+ \/ @% f5 D【输入格式】
' n" S* [0 B% f. g: H. N+ G* ]0 A
) t! S$ F' r8 `9 |+ L4 n' {        第一行包含两个整数 n 和 m。

$ n* Q" J3 \! K# n1 E+ O7 q        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

【输出格式】
, [! V& e' n7 P" m3 H7 I: D: B; M
6 ]' ]) u# \% C( N: H- l        输出一个整数，表示从左上角移动至右下角的最少移动次数。
: `7 D" m1 N+ e% C
. c/ g5 `+ m6 f+ [【数据范围】

5 e+ @. ]- b! m, {) H# u/ r        1≤n,m≤100
1 C% N0 V. Q6 U2 \
【输入样例】

5 5
& c0 W- V& m3 Y' O6 B0 1 0 0 0
+ u' {2 t5 d" V, Z0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】

8
【解题思路】
9 E$ @" S& Y: G
        BFS的典中典。

1. from collections import *
   ! {% ?% w  \( z+ I/ m
2. n,m = map(int,input().split())+ @\" w9 C% v4 E0 S. L+ G/ I$ i
   
3. mp = [[0]*(m+5)]  l/ ~( r2 M\" Z7 Y
   
4. for i in range(n):
   1 r2 i' u( R. F+ c, s3 B. T2 N: E
5.     mp.append([0]+list(map(int,input().split())))
   7 g# b  d' M% @& P, K
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   $ Z/ l% V: N) @: S8 u1 X
7. st = [[0]*(m+5) for _ in range(n+5)]
     R9 P  i4 d( _
8. def bfs():6 b6 e8 m; ~) {9 M6 o8 o
   
9.     q = deque()\" [% W1 |! D: Y1 h9 E0 w( d
   
10.     q.append([1,1,0])6 s8 ~1 m3 x& s' B( v3 ~6 i
    
11.     st[1][1]=1) N* Y# C' C6 O8 H0 M3 R; p
    
12.     while q:$ [% R8 O! l' N2 Q
    
13.         tx,ty,step = q.popleft()  f3 U- R9 C6 v3 D) _/ F
    
14.         if tx==n and ty==m:
    5 v) A, G* |6 N# u' v1 O
15.             print(step)
    8 i, U5 @5 N8 b0 G\" [
16.             return' C2 ^- `( ]2 u' N5 a% q6 M0 s\" @
    
17.         for x_,y_ in dir:) E1 k; c, Z1 ~1 W
    
18.             nx,ny = tx+x_,ty+y_
    + i- j: g3 B\" j3 X\" ^3 J
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    # N, `, \- l/ E
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ( T: K# Y; H\" g\" [3 U: d; d
21.             q.append( [nx,ny,step+1] )
    ) N+ U6 A\" c1 g7 c
22.             st[nx][ny]=1
    . V4 F\" o& L6 S9 C) u' t/ U
23. bfs()

复制代码

3 n# |- x# b& P$ a