数学建模社区-数学中国
标题:
python 走迷宫问题
[打印本页]
作者:
2744557306
时间:
2024-3-20 11:40
标题:
python 走迷宫问题
题目描述】
2 i8 z; i8 X! {, S5 S/ L
% @1 ~, j( {4 m9 @ C: p" r
给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
9 l6 F' @/ t! ]0 M( t- G) _% ^- E
4 @6 V' J* e O# h
【输入格式】
2 A( ?$ G+ L( M8 [1 h1 h* q4 ^2 T
0 L1 w' F. Z8 C6 X& T( S
第一行包含两个整数 n 和 m。
1 f1 y3 N0 V- G1 X
/ i& e. X$ o/ j6 |3 V6 k" R
接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
% J$ @; _% W* i- M7 l, b* I
! X% }9 q3 ]3 X# }
【输出格式】
* A# @: w9 S3 I& \/ R. L, Y/ n
4 v9 [ V, x. F' h. O; m& w- N' \
输出一个整数,表示从左上角移动至右下角的最少移动次数。
0 s6 n# ?3 F1 P! f* W5 q& U
& ^3 W) p7 L% I
【数据范围】
# l* g9 L: |0 X" ^% o5 S. o
7 y5 ?0 _0 I5 l; c
1≤n,m≤100
" q' c* q) s$ l' H0 F
+ Q, |4 ]5 V3 ~3 |+ h; u* k$ @1 w
【输入样例】
' h* v; [' E0 @8 ^4 [& U
$ {6 o9 I, U( a. W
5 5
* N! }3 D8 g4 v% J0 m4 Y
0 1 0 0 0
: K$ o6 W: J; B" n9 J9 x; m$ R
0 1 0 1 0
2 b* K& P4 \& H& W* P/ D' U5 G
0 0 0 0 0
0 C1 p! w: q6 `7 s8 j5 f
0 1 1 1 0
W0 E# @& f9 [* E) _9 Y* r0 v3 U
0 0 0 1 0
- D' g; ^, q. y J' G3 ~; n- C
【输出样例】
& S- G/ M# l& K
- }' i) U+ X* p& @
8
5 N; j" |. ?# \6 W* ?) q
【解题思路】
+ m+ V! y T8 a
& S; D% v d, F
BFS的典中典。
from collections import *
' `1 ^3 |1 @4 V* N: e3 k: o
n,m = map(int,input().split())
' M; S/ G, v- V. R
mp = [[0]*(m+5)]
. d- x: J( S- F% q2 |, p1 j
for i in range(n):
0 P) s5 c4 a) ~- P& U5 D0 V
mp.append([0]+list(map(int,input().split())))
+ x& e0 l" |/ M4 D! z
dir = [(1,0),(-1,0),(0,1),(0,-1)]
( c0 G5 a% H7 [: W
st = [[0]*(m+5) for _ in range(n+5)]
3 U1 F8 a9 D+ N! v6 `
def bfs():
1 v: O% }; E8 [
q = deque()
I t7 _4 W/ u2 R8 C3 H) p8 t
q.append([1,1,0])
7 c! o+ `# T, ^# y7 s( t8 G
st[1][1]=1
% p+ U5 D! b1 f% V( w
while q:
- m: y/ u+ }! I6 k! I y
tx,ty,step = q.popleft()
/ t# a9 B6 P& }
if tx==n and ty==m:
s$ }# [$ [! r% M( N: A T1 T" ]. L
print(step)
, t+ a2 w/ m8 ?" Y; J
return
/ j9 H; |& @% `
for x_,y_ in dir:
5 @4 V5 J% f: t
nx,ny = tx+x_,ty+y_
; A9 a. A1 z' C I8 g, n
if nx<1 or nx>n or ny<1 or ny>m:continue
. G1 [9 O- M" d3 \/ U' P
if mp[nx][ny]==1 or st[nx][ny]:continue
8 h' G1 e% L( H% Q* d# b4 U
q.append( [nx,ny,step+1] )
( Q9 R0 l7 ?3 g& K+ L' f
st[nx][ny]=1
& K9 P5 q# Y- b* Q) i
bfs()
复制代码
. n! m& H p) u% t* o, U% G ^, V
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5