python 走迷宫问题

2744557306

题目描述】
; t) n0 u$ L! R
( W' p" f+ G! i5 i* {1 H, L- D        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

: z# _3 m, G9 ^0 {/ U4 O' u5 k【输入格式】
7 b3 {( ^; h: K$ X: c
        第一行包含两个整数 n 和 m。
* k9 z. [6 X- k, x$ J2 u6 y
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
2 {8 C0 k+ C  Q  ~  Q2 l: \, M
6 q3 u, Q3 c$ h3 l4 x- A+ O【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
! v6 J) b  b  q) }- X
' O2 k; J7 s5 i7 @, G! n! k0 B5 _' I【数据范围】

; e! |2 B+ J& A3 U3 g( i        1≤n,m≤100

【输入样例】
! X# P1 N: A" B  a& `! D
5 5
0 1 0 0 0
0 1 0 1 0
+ A! ~8 c& m+ D* c! \  e1 U0 0 0 0 0
; ]/ R8 I# v1 R( a$ u+ E! ~, \0 1 1 1 0
0 0 0 1 0
& `# ^3 Z0 B: j1 H: q. u【输出样例】
: `  a* m* o8 D* v) b
8
$ N1 L; E3 u! { 【解题思路】

" W& p  D5 o9 ?        BFS的典中典。

1. from collections import *# T' {3 [\" Q3 j\" q0 \, f! G
   
2. n,m = map(int,input().split())\" b! A* E2 [% t+ O3 w
   
3. mp = [[0]*(m+5)]
   ! k) C* i$ K9 c; P. [4 a/ X
4. for i in range(n):
   & g8 G. C0 |) b
5.     mp.append([0]+list(map(int,input().split())))- m7 W: Y; T# t8 m( S+ M
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   9 T1 b/ G. ?- W, _% ?) a4 I
7. st = [[0]*(m+5) for _ in range(n+5)]: B4 i! q. z/ r& h. l
   
8. def bfs():
   # z\" X  L9 d/ @2 D$ z0 o
9.     q = deque()
   4 `( X. ^9 d& `' O9 Z4 Z# y
10.     q.append([1,1,0])3 R& y  p8 A3 j\" ?3 }
    
11.     st[1][1]=1
    5 A8 G) d' e9 t6 \% U8 q
12.     while q:
    - }5 y# |9 F* S( |( [; U\" }7 F
13.         tx,ty,step = q.popleft()5 l! B% j8 e& b  {
    
14.         if tx==n and ty==m:\" [% y4 P* l5 [* S3 Y' y, H+ A$ v
    
15.             print(step)* `2 U/ {2 [* Y. T: N
    
16.             return
    & B# Y: `, o3 B
17.         for x_,y_ in dir:
    ; A, O8 X3 V4 w8 s4 v2 Y
18.             nx,ny = tx+x_,ty+y_
    7 j. \8 B5 N3 }) `
19.             if nx<1 or nx>n or ny<1 or ny>m:continue: ]$ L\" `* [4 ~. X
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue$ O1 Z. Z6 F1 i# o3 y
    
21.             q.append( [nx,ny,step+1] )
    & J. m8 Q* q: [\" ^' T  d
22.             st[nx][ny]=12 \4 Y' f3 R6 v  T\" \
    
23. bfs()

复制代码

* S" [/ G$ o. C- T: c