python 走迷宫问题

2744557306

题目描述】

6 c! B6 f& d, E6 |; \        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
0 m7 L. d, g$ V5 W5 u8 H
4 M3 G5 z( ~% ^2 p1 r' f【输入格式】
! Z0 c; l" ~3 D3 T2 z
4 ?; m+ W& p; |' |5 Z+ \        第一行包含两个整数 n 和 m。
7 B% R0 G8 V) q7 b! k" B9 o" o9 n
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
$ e8 a* w( |6 F- e0 N( B' L* |5 I
: I5 [) [8 P, q% f& a7 w【输出格式】

# t& H) w$ Z, L        输出一个整数，表示从左上角移动至右下角的最少移动次数。

【数据范围】
( b: u0 K1 e! g9 M- \, ?
! t/ E0 a9 c+ G2 A: W        1≤n,m≤100

3 O6 A4 z+ h8 n: ?【输入样例】

5 5
0 1 0 0 0
2 d1 _( Z, M# z' |- {! t0 1 0 1 0
3 f% b0 O  u. H- h1 b+ i7 e0 0 0 0 0
0 1 1 1 0
1 R+ C, F6 }& k& J6 r; V: C0 0 0 1 0
( w! I2 W3 K) x; w' c8 M: v【输出样例】

7 _. u" i4 S" y. L8
* m1 N8 t6 {- o+ U' [ 【解题思路】
; g" N* U6 K: g: K: L* D
        BFS的典中典。

1. from collections import *) I6 M7 K. a( O+ A0 H# [9 e
   
2. n,m = map(int,input().split())' C2 F7 o: F5 }) o6 ^+ g
   
3. mp = [[0]*(m+5)]
   & f7 Q% \+ r6 J  d
4. for i in range(n):
   6 `! Y- t4 D. i2 M\" o+ U
5.     mp.append([0]+list(map(int,input().split())))! e& C; C, B9 ~! A0 t: [4 Q
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]\" r- M  c+ L6 g% ]\" I
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   6 y! G5 F8 ]- ?( n. S( Y8 @! k
8. def bfs():
   2 ?& C4 u, ^  m2 ~\" K6 C/ m2 o
9.     q = deque()8 w1 ]8 h+ P. a\" b9 B$ Z/ o8 s8 ]$ v
   
10.     q.append([1,1,0])
    9 J7 f0 n5 C/ m. }$ M
11.     st[1][1]=19 A& i' J\" L% g# G' l2 D) Y  I
    
12.     while q:
    : \% A; V3 n& l8 V: m
13.         tx,ty,step = q.popleft()' m7 G\" B\" t5 D( Y% T( N
    
14.         if tx==n and ty==m:- k$ E/ B% A. {* S% _
    
15.             print(step)
    # j( k+ b$ g% d\" z% Z
16.             return
    $ k  z7 D% V\" k  V( ]
17.         for x_,y_ in dir:
    / Q5 f* I$ c, t/ T$ V' W
18.             nx,ny = tx+x_,ty+y_
    9 c! p7 j) Y+ q# b1 R! I
19.             if nx<1 or nx>n or ny<1 or ny>m:continue( _( b; p6 d\" q. x7 _9 I* e+ e
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    8 k- i8 s: t# K- ]/ w4 H
21.             q.append( [nx,ny,step+1] )
    ' D2 L3 g% j3 G& `5 ?/ v
22.             st[nx][ny]=1
      \2 w$ Y8 }* h( z
23. bfs()

复制代码