python 走迷宫问题

2744557306

题目描述】

3 V) w2 v- o  E% M        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
# w. w/ j3 {( S( W
) [! u2 N& A5 j8 E4 h6 O1 N【输入格式】

        第一行包含两个整数 n 和 m。
# D! }- v  q8 x
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
- F' A* J: l6 y
5 S. M( D, K6 r9 ^( ^【输出格式】

4 g  y+ k# Q) \3 K3 h        输出一个整数，表示从左上角移动至右下角的最少移动次数。
, e1 C% {, C8 G- q  [; ?
# E$ f/ x0 {9 s【数据范围】

0 }; d. G5 J' N" c        1≤n,m≤100
, O- J5 {+ @/ _0 M& C% L% v
7 D- e8 b3 i" n8 |) h) c) ~【输入样例】
- k, T. |5 n# O+ g+ [( b0 ?
. d% O* S; O2 w! W" Q3 \+ C2 [, N- v5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
: M) E4 p3 ~6 |  W! O0 1 1 1 0
( `. y, C; u+ b( `4 a0 0 0 1 0
- m: n( ?& }0 X  ]9 Y) y& G; }6 t【输出样例】

8
【解题思路】
+ v- a, {; e: T; \. Y; N
! |4 K( ~2 D& Y! S        BFS的典中典。

1. from collections import *
   1 }& m1 ?( Z% b1 u3 b# K  j\" h
2. n,m = map(int,input().split())
   4 i9 ~: f0 D7 U1 M\" Y+ m
3. mp = [[0]*(m+5)]7 a/ r6 D; h0 a- F$ ~6 }/ }# D; V. ?
   
4. for i in range(n):
   : l/ J  }# `, L( b! C
5.     mp.append([0]+list(map(int,input().split())))
   $ `8 ]3 a. F1 n; f
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]$ a; A. `% }- W3 N  T
   
7. st = [[0]*(m+5) for _ in range(n+5)]: k6 O& u* |/ P  @8 q
   
8. def bfs():, B7 r6 W* K* [, _4 U
   
9.     q = deque()
   # c\" p; X! z  e
10.     q.append([1,1,0]); z* C. _2 B# L5 f- Q5 D9 M( J* m
    
11.     st[1][1]=16 d: w6 U' P8 F6 e5 ?5 f8 j% n
    
12.     while q:: i/ Z, g. o5 \: S, B
    
13.         tx,ty,step = q.popleft()  D* d2 o; D) ~$ L
    
14.         if tx==n and ty==m:
    , a# m  }# H1 ]8 M8 Y# q
15.             print(step)9 N1 d8 ?# l1 P7 f9 s! s( S
    
16.             return  \. c: s1 `7 c1 f; R
    
17.         for x_,y_ in dir:) W* c! @' c5 L: q* F) v) L8 c
    
18.             nx,ny = tx+x_,ty+y_. U( U; x0 T* e
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    & k3 C$ U' q5 f/ f) m\" M
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    8 T: O1 T) Z% N) r% W4 N8 ]2 |/ i
21.             q.append( [nx,ny,step+1] )5 F8 Z8 S% W! x0 H2 O6 L
    
22.             st[nx][ny]=1
    4 r- ~; T+ A- E. }& }5 x
23. bfs()

复制代码

" @) c: `, |9 N