数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】
% ~% W! Z( r7 a* P6 B' ]4 s  ~+ r2 o+ W7 q& a, r$ ~
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
7 W# M) C0 e. T) d* U
0 R( e, D7 R9 R- H  c4 z" L【输入格式】) c/ D! g; h& e( _2 l2 d
2 F: r8 N" N6 r
        第一行包含两个整数 n 和 m。
; T, Q6 i  R5 q; k" \2 q% ]1 w' P% d, I# }5 d6 K
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。8 n. }% G1 X$ l0 t! D4 i

  I9 k4 d; X3 t! y( S9 p+ o【输出格式】
& M  A& _, f0 I3 J
6 l1 a& ^0 L6 D6 A        输出一个整数，表示从左上角移动至右下角的最少移动次数。+ B7 l* ^8 {9 v* L* ^3 A9 S

8 z, V, N' V& e' L: F7 j0 u# Q【数据范围】0 i5 b+ P+ C9 N" G  n

; J( i) e; c" Q7 c6 e' ~- b        1≤n,m≤100
. z" G2 O" {: \% O& S4 H  B9 Y- o; N+ X, G( a/ ]0 f
【输入样例】
/ i9 M8 }( V) \  X( k* C+ Y" Y
7 C0 M# c' ~, m3 x' b; _. M5 5( D" r/ o$ u$ z9 u  F/ \: T
0 1 0 0 0
+ a( P# T/ t2 L$ [0 1 0 1 0
8 U- N1 R3 P: |0 0 0 0 0
$ K# k  b5 K& Q0 1 1 1 0) N) [! [) `1 T/ g
0 0 0 1 0
2 b. L( R$ \/ m) C6 V【输出样例】
: o" o3 d  k' E* P* B( Y2 E8 J: ?0 l8 G+ c8 Y
8
2 Q0 M" a$ t* F; D  F1 e3 _0 \7 P4 } 【解题思路】1 U% L/ l4 [2 e9 ~
3 ~+ H/ O# k$ o' F  a* F, _8 q) H
        BFS的典中典。
  1. from collections import *% e5 `* X5 W( l3 h
  2. n,m = map(int,input().split())+ ~+ l) E- z0 [+ ~* M4 g& g( _: Q
  3. mp = [[0]*(m+5)]
    ) e1 W* x( M5 M- ^
  4. for i in range(n):$ T9 l! i( J2 I; Z# H9 z( Y. v! ~
  5.     mp.append([0]+list(map(int,input().split())))) U: G7 ~7 g) s( u* j4 l3 g
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
    4 z; D0 j8 o6 U* C/ V( c
  7. st = [[0]*(m+5) for _ in range(n+5)]
    - ]7 c1 U7 x, s* P) ~
  8. def bfs():
    ; H" d: D& M$ f
  9.     q = deque()
    , ~# f6 ^; p1 @: h
  10.     q.append([1,1,0])
    % \0 m5 A% ~) [  g0 k
  11.     st[1][1]=1
    5 e: q: g$ H% [+ H
  12.     while q:
    0 n2 l# O( h! b- m
  13.         tx,ty,step = q.popleft()
    - l& ]% K" n7 [- K3 Z
  14.         if tx==n and ty==m:
    8 k: _% {# b& ^
  15.             print(step)( ?9 l! _7 X) x! x8 }* c$ a+ j
  16.             return
    1 t) V& W5 I4 Y
  17.         for x_,y_ in dir:# t0 w# e: D' o
  18.             nx,ny = tx+x_,ty+y_
    0 W. k1 ~* N4 X+ H
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue% e; x, A0 f' T: x
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue, v2 l5 |6 h4 J0 [5 ]) L. }" S
  21.             q.append( [nx,ny,step+1] )
    ) ]: C3 A1 @/ r9 Q
  22.             st[nx][ny]=1
    & {8 |* B" m5 E0 {3 Q9 g
  23. bfs()
复制代码
% \- V& p  {+ g( o- K




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