python 走迷宫问题

2744557306

题目描述】

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

) ^: Y: @3 R9 p) G% U! r  y【输入格式】

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

- c% b" C3 @2 ?% ?: o        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
  a! c6 t, y- Z! Y( j% N1 N# {  z  u
【输出格式】

( w( c" l2 X" h- l2 Y9 d1 K$ C        输出一个整数，表示从左上角移动至右下角的最少移动次数。
5 K6 z7 z( j# v5 X2 `
【数据范围】

' p) R0 D# D/ A* ^' j* L: a        1≤n,m≤100
8 q' e6 h; X4 O* C5 H
) N- u4 A6 P3 V# m【输入样例】
# D3 H$ ^1 S( b# Y& V6 U
5 5
0 1 0 0 0
1 a( h* ?+ F  S+ y6 j/ T$ N0 1 0 1 0
, V8 _) ?' r- i: W7 P: U' q) D. ^0 0 0 0 0
% z* O: ^1 C' h: C0 1 1 1 0
0 0 0 1 0
" |0 ~! N2 ], Z. A【输出样例】

+ p& K6 \! z; K8
. z9 C0 ^" W  h9 ]* }1 e" F& ]9 N 【解题思路】

: p0 X/ F( t8 }2 f( e3 @        BFS的典中典。

1. from collections import *. {1 c: {# ~& K6 I% K0 w
   
2. n,m = map(int,input().split())
   4 T6 K$ Z$ ]/ N# o  \+ F
3. mp = [[0]*(m+5)]
   . w( i; F\" ?. B
4. for i in range(n):& J: ]+ V% ?7 L\" l
   
5.     mp.append([0]+list(map(int,input().split()))), r9 z% P) a  v/ g, x\" j: R, @
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]8 a- c8 @/ i  x/ d9 Y* m/ q
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   ) x+ f+ L' n# O% M3 J! ]
8. def bfs():2 F' Y3 d8 ]% j( h
   
9.     q = deque()% A2 g( D7 M+ _# C
   
10.     q.append([1,1,0])# {0 o, f0 f; d* u- u8 l
    
11.     st[1][1]=1
    ( W# _2 q! z8 K
12.     while q:/ k! _7 z, R\" W( a+ t/ y4 f
    
13.         tx,ty,step = q.popleft()
    \" V% {& u2 A+ n3 |4 F$ i& U
14.         if tx==n and ty==m:
    - n' `; q4 p, d6 d+ B
15.             print(step)+ K- R3 D6 C0 @/ x4 B: N9 p! K
    
16.             return( u2 C+ a- O2 i+ j2 w3 r4 E
    
17.         for x_,y_ in dir:
    ! a4 ?. b/ [' e& W7 @/ B* Z2 {
18.             nx,ny = tx+x_,ty+y_1 ^6 Y9 Y\" j& p' z& g. @4 v& W( q
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    \" y$ D! [. j6 r% o4 [9 t
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ; f' N. G0 R! }\" \. Y0 q4 w% v
21.             q.append( [nx,ny,step+1] )
    8 x7 g& p  z1 d0 f
22.             st[nx][ny]=1
    ; f. |& F3 D6 H
23. bfs()

复制代码

* s* x2 Q. W* I, `  ^$ v