QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2635|回复: 0
打印 上一主题 下一主题

python 走迷宫问题

[复制链接]
字体大小: 正常 放大

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-20 11:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
题目描述】  D$ U  y/ a' S& w$ h9 l6 p
' _1 e6 E7 B! _. O
        给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。3 t2 r# O! k( }3 J$ A

) ^: Y: @3 R9 p) G% U! r  y【输入格式】+ t, |$ h% h3 a4 n7 ]' T8 ~  T6 U+ [
- D# `3 }7 S, V
        第一行包含两个整数 n 和 m。  o' v- }8 K4 }! f* a& ^5 J

- c% b" C3 @2 ?% ?: o        接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
  a! c6 t, y- Z! Y( j% N1 N# {  z  u3 f* C  ]  y* Z
【输出格式】3 m, q2 k; f( L. r

( w( c" l2 X" h- l2 Y9 d1 K$ C        输出一个整数,表示从左上角移动至右下角的最少移动次数。
5 K6 z7 z( j# v5 X2 `, G, P) o2 @- I+ `# j- G+ v$ U# J0 I
【数据范围】! ~2 u, `5 d7 T6 [

' p) R0 D# D/ A* ^' j* L: a        1≤n,m≤100
8 q' e6 h; X4 O* C5 H
) N- u4 A6 P3 V# m【输入样例】
# D3 H$ ^1 S( b# Y& V6 U0 y: t7 E2 r( I1 Z! |
5 5/ \/ R* M+ F7 X8 A* I, r7 t: P
0 1 0 0 0
1 a( h* ?+ F  S+ y6 j/ T$ N0 1 0 1 0
, V8 _) ?' r- i: W7 P: U' q) D. ^0 0 0 0 0
% z* O: ^1 C' h: C0 1 1 1 0" i. Q& K) k& `8 b
0 0 0 1 0
" |0 ~! N2 ], Z. A【输出样例】; {  g) p- F9 C, C

+ p& K6 \! z; K8
. z9 C0 ^" W  h9 ]* }1 e" F& ]9 N 【解题思路】. Y3 m, D' o0 j/ g) Z

: p0 X/ F( t8 }2 f( e3 @        BFS的典中典。
  1. from collections import *. {1 c: {# ~& K6 I% K0 w
  2. n,m = map(int,input().split())
    4 T6 K$ Z$ ]/ N# o  \+ F
  3. mp = [[0]*(m+5)]
    . w( i; F\" ?. B
  4. for i in range(n):& J: ]+ V% ?7 L\" l
  5.     mp.append([0]+list(map(int,input().split()))), r9 z% P) a  v/ g, x\" j: R, @
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]8 a- c8 @/ i  x/ d9 Y* m/ q
  7. st = [[0]*(m+5) for _ in range(n+5)]
    ) x+ f+ L' n# O% M3 J! ]
  8. def bfs():2 F' Y3 d8 ]% j( h
  9.     q = deque()% A2 g( D7 M+ _# C
  10.     q.append([1,1,0])# {0 o, f0 f; d* u- u8 l
  11.     st[1][1]=1
    ( W# _2 q! z8 K
  12.     while q:/ k! _7 z, R\" W( a+ t/ y4 f
  13.         tx,ty,step = q.popleft()
    \" V% {& u2 A+ n3 |4 F$ i& U
  14.         if tx==n and ty==m:
    - n' `; q4 p, d6 d+ B
  15.             print(step)+ K- R3 D6 C0 @/ x4 B: N9 p! K
  16.             return( u2 C+ a- O2 i+ j2 w3 r4 E
  17.         for x_,y_ in dir:
    ! a4 ?. b/ [' e& W7 @/ B* Z2 {
  18.             nx,ny = tx+x_,ty+y_1 ^6 Y9 Y\" j& p' z& g. @4 v& W( q
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    \" y$ D! [. j6 r% o4 [9 t
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ; f' N. G0 R! }\" \. Y0 q4 w% v
  21.             q.append( [nx,ny,step+1] )
    8 x7 g& p  z1 d0 f
  22.             st[nx][ny]=1
    ; f. |& F3 D6 H
  23. bfs()
复制代码

* s* x2 Q. W* I, `  ^$ v
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-6-16 09:50 , Processed in 0.454556 second(s), 51 queries .

回顶部