数学建模社区-数学中国
标题:
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* E
0 ]* 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, d
5 5
4 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 N
0 0 0 0 0
$ i) a9 I8 ]2 n5 o+ h* O
0 1 1 1 0
3 [# {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的典中典。
from collections import *
/ L9 [1 E1 [5 E: d4 x$ x. [
n,m = map(int,input().split())
* ^- F9 s& G1 Q$ N& ~
mp = [[0]*(m+5)]
, s5 Z9 y1 O6 D3 w7 d9 L/ ^4 n- L) K* l
for i in range(n):
( R# y+ t+ j; I
mp.append([0]+list(map(int,input().split())))
+ `1 P! ?& N- l; k o
dir = [(1,0),(-1,0),(0,1),(0,-1)]
' T. x3 v8 w: [# {5 K7 R9 O
st = [[0]*(m+5) for _ in range(n+5)]
& O! N6 x* |/ g- C5 P
def bfs():
+ R( n; a) y! H6 v3 ~* {7 G
q = deque()
; A2 ^$ ?/ b4 P, p5 }+ T! V
q.append([1,1,0])
) X& p) Z5 I) I8 f7 e9 D2 U
st[1][1]=1
- r; C+ C! |) b8 N- f2 T2 ?
while q:
) N; f7 J: u) Z" f7 Y
tx,ty,step = q.popleft()
5 v8 V6 g& K% N6 [2 K
if tx==n and ty==m:
5 D- S( f3 ~8 N
print(step)
+ o+ x. U3 r* N6 a. N. F% _1 w) L
return
8 B. ?$ U% ?7 x0 b6 P( `: d
for x_,y_ in dir:
. a" F5 p9 q9 g" T" s; u1 q
nx,ny = tx+x_,ty+y_
I3 o; m2 G) t5 e1 `4 ~
if nx<1 or nx>n or ny<1 or ny>m:continue
" I: P/ \ Y* H1 n+ W
if mp[nx][ny]==1 or st[nx][ny]:continue
) y) j) \+ i' u2 j/ s2 t# r" |
q.append( [nx,ny,step+1] )
7 D4 E- d" a$ X9 c* r/ k+ L
st[nx][ny]=1
0 Z0 h6 H+ {2 G! |
bfs()
复制代码
; K) U0 N' v+ E, Z! i9 X! y6 f, W; z
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5