python 走迷宫问题

2744557306

题目描述】

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

' b4 r" ?2 V2 n  A" z( g+ Y1 e6 J【输入格式】

6 L) ~4 ^5 y7 R) s7 l8 I        第一行包含两个整数 n 和 m。

+ p- ?% {0 V' h% v/ G! _8 V, `        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
6 e$ [) B$ g! D0 X
【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。

1 F& x0 }/ k9 Y# o0 _) I【数据范围】

        1≤n,m≤100

【输入样例】

5 5
/ s, U8 B; O4 w8 t0 1 0 0 0
: R3 ]8 p* @- v# T" h7 c* ~% v; v0 1 0 1 0
0 0 0 0 0
8 x" n# r5 L! G) Q8 H; W0 1 1 1 0
; B" q* F+ D& K0 0 0 1 0
4 j  d9 \/ v. T# ~! v+ r【输出样例】

8
4 l6 I3 f& k" l, N% e# _; }8 O; n 【解题思路】
$ P6 Z4 X4 [; z) J" o
6 d5 i# ?3 A( q        BFS的典中典。

1. from collections import *
   / I5 F# Z( f0 d  R9 V5 C
2. n,m = map(int,input().split())
   0 k# V- B* u- I( S& _; C( y; j
3. mp = [[0]*(m+5)]* A; B: u* M+ p9 z* S
   
4. for i in range(n):# a. B2 t4 n; }3 K
   
5.     mp.append([0]+list(map(int,input().split())))$ N4 q6 B# E( h( ]
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]  y0 G\" e1 E. ^\" w7 r, G- }
   
7. st = [[0]*(m+5) for _ in range(n+5)]
   + d; y# k  l9 _$ u! H
8. def bfs():+ R: @3 E  X6 b
   
9.     q = deque()
   9 d( m\" `# m4 S' ?% B( B: a
10.     q.append([1,1,0])
    \" }) C# o/ y7 U5 q8 P+ N! N
11.     st[1][1]=19 y- e' S1 X\" e2 O( X
    
12.     while q:& [. G. |; ^8 Z
    
13.         tx,ty,step = q.popleft()
      z* O% {4 g( e, u: O
14.         if tx==n and ty==m:
    \" k# A6 ?/ P/ y- k( E' ]1 M
15.             print(step)
    * Y% D% `  R. ~8 ]
16.             return
    * U* _8 u4 c( [# Q. g
17.         for x_,y_ in dir:
    ; a\" E+ F* Q2 _: _\" L
18.             nx,ny = tx+x_,ty+y_\" }8 A( v; e- d9 R% l& o# X. d$ h
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    9 G9 t6 F/ b, B, F9 L' t
20.             if mp[nx][ny]==1 or st[nx][ny]:continue6 q, o0 `# k+ P* u  K
    
21.             q.append( [nx,ny,step+1] )4 N/ |* g6 G0 s! R( m' ?
    
22.             st[nx][ny]=1/ `/ S( i8 R( r\" C+ \
    
23. bfs()

复制代码

* N! `8 t# v% H