python 走迷宫问题

2744557306

题目描述】
6 b. l1 o8 Z6 J0 s5 D- F, I
5 f3 D$ ^, ~  E* h        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
" g4 {" g% `1 J4 g1 q% C2 ?
2 R2 R( d: v" J【输入格式】

) j' W  G, u1 h* X! H; W5 I        第一行包含两个整数 n 和 m。
* _2 m1 ^+ a& S$ b( E
5 G. v8 M% ~7 d# T( |7 C        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
% p  W! q9 Q) y6 n' I' x; R
【输出格式】

8 E- v# v. i  h3 U7 c        输出一个整数，表示从左上角移动至右下角的最少移动次数。

) c8 _# K+ s" n! d' k: v【数据范围】
& a4 C- H) a8 J1 P( l  B7 w4 g
        1≤n,m≤100
$ Y- ]$ V5 O: Z" o# o
【输入样例】

5 5
% k- u0 K8 k: `# O( z0 1 0 0 0
1 d2 X' y2 W4 b9 q/ v/ g7 K7 y0 1 0 1 0
# u3 f1 ~) U2 h( v, d0 0 0 0 0
" k- k" \/ ?4 Z  X! ^( @0 1 1 1 0
0 0 0 1 0
0 Y# F, @; t6 Q3 F- \. Q【输出样例】
3 A1 v5 @- _- L* \1 n! v, p
  H& R6 M: q- H2 r5 `8
5 K: a) d# r8 O4 \+ u- B 【解题思路】

        BFS的典中典。

1. from collections import *
   # {9 s0 X) L6 X3 k  n! g* l$ t
2. n,m = map(int,input().split())* ^! a5 E3 [: G\" g\" i
   
3. mp = [[0]*(m+5)]1 N$ d' r) w( \7 t( f
   
4. for i in range(n):+ _. U! T- _9 w
   
5.     mp.append([0]+list(map(int,input().split())))9 e! x- G0 S5 C. L% k* u2 Y
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]/ Q$ c9 l: ~9 o* b3 s# z
   
7. st = [[0]*(m+5) for _ in range(n+5)]\" ]* T# P! E; `
   
8. def bfs():; X7 ~2 C) e  Z: @
   
9.     q = deque()' E. l' M6 o: b8 n& h
   
10.     q.append([1,1,0])0 }( D% |* Q# W+ N/ J; A
    
11.     st[1][1]=1
    ) r! }+ Q# \: H3 t  _
12.     while q:! ^8 z: l* Y( s# i+ p
    
13.         tx,ty,step = q.popleft()' D; e# k\" e* N9 d% ^2 b7 k# Q! a
    
14.         if tx==n and ty==m:
    # G1 V1 U/ Z! I% m  m
15.             print(step)
    9 Z5 H3 B( L1 L
16.             return& E  \. O$ L) D) t
    
17.         for x_,y_ in dir:
    \" j  Q3 x. O+ S7 e* O9 |# V& h
18.             nx,ny = tx+x_,ty+y_0 ^* I( i\" q8 z/ v, ^1 @
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue5 a; V6 |1 _, L
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue! y2 c- v( H! y8 V2 b. Z& B/ i
    
21.             q.append( [nx,ny,step+1] )
    & w& w  y& L; Y& A) u- T) w; \
22.             st[nx][ny]=14 S& A2 H; I7 x1 ?' @
    
23. bfs()

复制代码