数学建模社区-数学中国
标题:
python 走迷宫问题
[打印本页]
作者:
2744557306
时间:
2024-3-20 11:40
标题:
python 走迷宫问题
题目描述】
" g* W, K6 v; A' `( R+ h+ ]& h
4 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 k
0 1 0 1 0
' k9 f- U) P9 G* u9 M
0 0 0 0 0
2 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的典中典。
from collections import *
+ T( K. a' e) Z4 K4 N0 P+ v4 ~
n,m = map(int,input().split())
' d; W. F1 Y! [' H0 v* E Z
mp = [[0]*(m+5)]
) m3 l9 R! K& t1 [5 x
for i in range(n):
( z, Z/ ~) b+ V. f9 r, u
mp.append([0]+list(map(int,input().split())))
$ [/ a3 j: u# C. l
dir = [(1,0),(-1,0),(0,1),(0,-1)]
3 k1 b" y- ?: j# z5 o9 d
st = [[0]*(m+5) for _ in range(n+5)]
& p$ z/ d* h7 _; G
def bfs():
6 \/ `7 A% J3 ~ U
q = deque()
0 H! ~3 ^2 O: }4 S8 s! ]
q.append([1,1,0])
. E# m* `2 c, J: ~6 o7 ~7 N
st[1][1]=1
% k; U& I: u& j: B
while q:
3 h0 o7 l; N: s. [, N4 t: `( y
tx,ty,step = q.popleft()
: h( ]" q; h* T
if tx==n and ty==m:
9 y- H: z5 l# l# |$ E+ P
print(step)
1 ^" i) @5 f# S6 X3 [7 }6 L
return
8 f& o; H% H) N. R
for x_,y_ in dir:
, |& Z: I2 U' r" S
nx,ny = tx+x_,ty+y_
]. F. @* `4 B4 X! A' r5 n
if nx<1 or nx>n or ny<1 or ny>m:continue
! Z: ^3 s! t5 S l
if mp[nx][ny]==1 or st[nx][ny]:continue
3 M3 a( G- Z& h( Y) w
q.append( [nx,ny,step+1] )
2 M9 q: W: o- y7 ~
st[nx][ny]=1
. ]9 Z2 P$ d# r2 a: h) k) o
bfs()
复制代码
! L0 w6 u9 m5 n8 w* P4 _3 X
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5