数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】
" g* W, K6 v; A' `( R+ h+ ]& h4 T& \, w4 \+ s8 |7 K/ K
        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。2 G" s$ ]) R; O/ O1 Q
# T; o! K/ c9 q
【输入格式】
9 k. x% w' |7 R+ `7 `( p
/ y! |. ]9 I/ a3 L7 M: I        第一行包含两个整数 n 和 m。7 _0 [# e3 y+ O/ v
/ Z" {$ O+ s9 M& G' Q4 J, ^
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。& D7 Z6 A$ ^: u3 R$ N1 V

# o3 v, v4 l* T2 A【输出格式】9 z: E: X6 G6 j

6 _3 ~# h  ?$ \9 ^        输出一个整数，表示从左上角移动至右下角的最少移动次数。' f% b. E' y3 d- P/ t1 i' R. Y  e
& |7 M7 l0 @$ I6 l
【数据范围】; k7 W; ~5 i: v+ I
2 ?' S' K/ I) j
        1≤n,m≤100" C7 h, h2 }( Y  ~" O3 |# Z- s
4 h, [: G. j! m5 Y4 ~
【输入样例】
. L6 O, T# h  ~* x# A, U& J0 g- [+ p
5 5: L2 H  ?* J! \2 \$ k7 E
0 1 0 0 0
4 S6 h& z7 M5 k0 1 0 1 0' k9 f- U) P9 G* u9 M
0 0 0 0 02 d5 c8 B, v' V( J. j  a
0 1 1 1 0( w* V4 g4 d0 [5 W. C4 F
0 0 0 1 0; K2 Q& d6 k( F
【输出样例】" \8 u% {' ]) ]! x  B
" @) C1 a5 l& M, h7 O
8* k1 T/ E4 [& _6 V
【解题思路】
) g1 r' B" L, Z* l; W
1 C/ A/ e/ V/ P& i' m        BFS的典中典。
  1. from collections import *+ T( K. a' e) Z4 K4 N0 P+ v4 ~
  2. n,m = map(int,input().split())
    ' d; W. F1 Y! [' H0 v* E  Z
  3. mp = [[0]*(m+5)]
    ) m3 l9 R! K& t1 [5 x
  4. for i in range(n):
    ( z, Z/ ~) b+ V. f9 r, u
  5.     mp.append([0]+list(map(int,input().split())))
    $ [/ a3 j: u# C. l
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
    3 k1 b" y- ?: j# z5 o9 d
  7. st = [[0]*(m+5) for _ in range(n+5)]& p$ z/ d* h7 _; G
  8. def bfs():6 \/ `7 A% J3 ~  U
  9.     q = deque()0 H! ~3 ^2 O: }4 S8 s! ]
  10.     q.append([1,1,0]). E# m* `2 c, J: ~6 o7 ~7 N
  11.     st[1][1]=1% k; U& I: u& j: B
  12.     while q:
    3 h0 o7 l; N: s. [, N4 t: `( y
  13.         tx,ty,step = q.popleft(): h( ]" q; h* T
  14.         if tx==n and ty==m:
    9 y- H: z5 l# l# |$ E+ P
  15.             print(step)1 ^" i) @5 f# S6 X3 [7 }6 L
  16.             return
    8 f& o; H% H) N. R
  17.         for x_,y_ in dir:, |& Z: I2 U' r" S
  18.             nx,ny = tx+x_,ty+y_  ]. F. @* `4 B4 X! A' r5 n
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue! Z: ^3 s! t5 S  l
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue3 M3 a( G- Z& h( Y) w
  21.             q.append( [nx,ny,step+1] )2 M9 q: W: o- y7 ~
  22.             st[nx][ny]=1
    . ]9 Z2 P$ d# r2 a: h) k) o
  23. bfs()
复制代码

! L0 w6 u9 m5 n8 w* P4 _3 X



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