数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】
0 [- H' Y+ Z) C# Y! s* c; }% K2 l
. k3 U: O- |" @' _2 Q  U: K7 i5 r        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
2 U( R6 r# d2 J3 N# `, r, N* E0 ]* R3 I  J& A9 q9 j( l* F0 W
【输入格式】4 t2 s6 c% I5 W; ^9 U# W

( d% E/ O9 S4 {) Y; \        第一行包含两个整数 n 和 m。4 v, e2 c; ], h( b! A) O
  \6 S/ [; x% ?) A" ~( I6 M1 Z
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
9 S2 b! ?. x6 Q, ~! D( Q0 A  B
- f" h7 Y# q5 m2 G8 r, g【输出格式】8 Q" `- a8 ?: R$ ^5 R
: d- G+ m- v$ ?
        输出一个整数，表示从左上角移动至右下角的最少移动次数。: k. v3 y2 i0 c. d2 e- |$ n

% {' O1 Y& ^$ j【数据范围】
/ b" d( V  X, W# E$ i# @3 p
! Y; ?/ U+ A. C        1≤n,m≤100
; k: y& ]- U% _) l! L9 K% W: |8 F' c* K( _8 {6 Q# M; K
【输入样例】  c3 T6 d% @+ e! s/ s9 y2 s

' K% A9 ~- u* q, d5 54 Z* ?. N, f$ ]5 R0 E# l4 ^
0 1 0 0 0% S6 q$ j: |" f; \
0 1 0 1 0
( E% J+ f& \4 D  S3 N0 0 0 0 0$ i) a9 I8 ]2 n5 o+ h* O
0 1 1 1 03 [# {7 T  u5 r) @$ |
0 0 0 1 0% [. r+ ~7 Q# q
【输出样例】2 W, d- d2 F* f5 Y" a( E
& I$ }+ A' K* _
8
( r/ G! R( ]1 v. ?- [( E 【解题思路】5 ^/ L, ^  F; T$ r0 G' ]/ ?
4 a: @; s! [$ V" D+ K
        BFS的典中典。
  1. from collections import */ L9 [1 E1 [5 E: d4 x$ x. [
  2. n,m = map(int,input().split())* ^- F9 s& G1 Q$ N& ~
  3. mp = [[0]*(m+5)]
    , s5 Z9 y1 O6 D3 w7 d9 L/ ^4 n- L) K* l
  4. for i in range(n):
    ( R# y+ t+ j; I
  5.     mp.append([0]+list(map(int,input().split())))+ `1 P! ?& N- l; k  o
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]' T. x3 v8 w: [# {5 K7 R9 O
  7. st = [[0]*(m+5) for _ in range(n+5)]& O! N6 x* |/ g- C5 P
  8. def bfs():+ R( n; a) y! H6 v3 ~* {7 G
  9.     q = deque(); A2 ^$ ?/ b4 P, p5 }+ T! V
  10.     q.append([1,1,0])
    ) X& p) Z5 I) I8 f7 e9 D2 U
  11.     st[1][1]=1- r; C+ C! |) b8 N- f2 T2 ?
  12.     while q:) N; f7 J: u) Z" f7 Y
  13.         tx,ty,step = q.popleft()5 v8 V6 g& K% N6 [2 K
  14.         if tx==n and ty==m:5 D- S( f3 ~8 N
  15.             print(step)
    + o+ x. U3 r* N6 a. N. F% _1 w) L
  16.             return
    8 B. ?$ U% ?7 x0 b6 P( `: d
  17.         for x_,y_ in dir:
    . a" F5 p9 q9 g" T" s; u1 q
  18.             nx,ny = tx+x_,ty+y_
      I3 o; m2 G) t5 e1 `4 ~
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue" I: P/ \  Y* H1 n+ W
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ) y) j) \+ i' u2 j/ s2 t# r" |
  21.             q.append( [nx,ny,step+1] )7 D4 E- d" a$ X9 c* r/ k+ L
  22.             st[nx][ny]=10 Z0 h6 H+ {2 G! |
  23. bfs()
复制代码
; K) U0 N' v+ E, Z! i9 X! y6 f, W; z




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5