python 走迷宫问题

2744557306

题目描述】

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

4 \* ^+ h& s6 u3 \7 K! s% ~【输入格式】

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

' P# Y% m" b6 e# P- Z1 F        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
4 f) M, \* n5 F
【输出格式】

        输出一个整数，表示从左上角移动至右下角的最少移动次数。
/ V1 s& p. l% w/ M# d+ U4 L# c
6 Y! o6 W' |+ ?$ A) t6 f& _, z, Q【数据范围】

% _8 d6 p1 j6 i+ b7 t        1≤n,m≤100
+ }3 H9 d0 m3 P' p% g. U- c& z
【输入样例】
: r  T$ U( }' u( M
5 5
0 1 0 0 0
0 1 0 1 0
7 H& b: _, z( L0 j: ]; l; R& A0 0 0 0 0
0 1 1 1 0
0 @( V* ^& c3 H/ }; c4 v0 0 0 1 0
! C) x; X2 C  B% Z& l* ^9 p6 M【输出样例】

8
【解题思路】

. A* H. T9 `- A; C        BFS的典中典。

1. from collections import *4 x* s9 |: `* U' S8 t\" x
   
2. n,m = map(int,input().split())
   . q' H3 b. A6 Z) u/ f
3. mp = [[0]*(m+5)]
   $ ~# n+ R2 C$ h7 C$ A7 ]( \- g' A+ l
4. for i in range(n):
   3 h3 G- a+ @/ o. }$ w. @0 t
5.     mp.append([0]+list(map(int,input().split())))8 H: R0 n) i$ o+ N8 c0 q. V3 }- y
   
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]- ]$ i# T5 z+ w5 b  i( }
   
7. st = [[0]*(m+5) for _ in range(n+5)]) ]% G$ W+ `. P5 U% V
   
8. def bfs():\" O: Z5 u! p( b3 |
   
9.     q = deque()
   7 J' y6 s( m1 O9 G3 x( C7 P7 Y
10.     q.append([1,1,0])9 V8 o) B2 m1 A/ i
    
11.     st[1][1]=1: a$ Y4 J5 s; Q3 O, W
    
12.     while q:
    , K\" ]9 t1 F& S% Y* e
13.         tx,ty,step = q.popleft(). w4 i/ K4 j. d* p+ Z
    
14.         if tx==n and ty==m:/ \; U/ Y6 O\" z& {4 D1 Y2 H$ N
    
15.             print(step)
    7 s\" }( r3 F$ r- {( y  B, w
16.             return! g* h5 T1 D3 w, K2 K5 M$ Q
    
17.         for x_,y_ in dir:
    2 q6 T8 z/ i; G, ^
18.             nx,ny = tx+x_,ty+y_
    \" E; {0 r! ]4 S  A$ ]
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    ' t( P( @* P( l9 j
20.             if mp[nx][ny]==1 or st[nx][ny]:continue- n2 Q+ b; C* t# R0 V* h; z) T
    
21.             q.append( [nx,ny,step+1] )
    \" Q; i: `; o& p) T: P\" h2 T
22.             st[nx][ny]=1% U5 z$ r9 O7 f. f& N4 p
    
23. bfs()

复制代码