QQ登录

只需要一步,快速开始

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

python 走迷宫问题

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

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-20 11:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
题目描述】0 q, w7 D* D. {* T) k" j& p

4 m3 I. d1 w5 Z7 Q. t        给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
2 `! K$ }/ O, {9 p2 E0 X* B2 Z5 z! M4 x. V% B8 T1 `
【输入格式】
4 w3 D0 A/ @. ~0 S: p" O3 I
# Q4 C2 A4 M/ ?( c: v        第一行包含两个整数 n 和 m。- l2 ?3 b! a2 C+ j! B' U

( M' U$ H" K4 _2 y0 f        接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。! p" {( ^: S; u/ y9 n1 [

$ g7 x$ D3 I: ^【输出格式】3 t9 o" v& B/ s. U
+ z0 _) W& @8 ~" b
        输出一个整数,表示从左上角移动至右下角的最少移动次数。: y/ M. H/ r( r# }3 T8 F
% U( D4 U$ s. L7 B' N
【数据范围】4 u0 q: i# c# m) F7 ^
0 U" v6 Q3 O0 Y6 S# }
        1≤n,m≤100% |% Z  j! Z8 D/ S% t% o
' `* {3 @6 |) b8 r% c6 l
【输入样例】
$ x& ?+ c2 L2 _; ~9 u4 `( [# ^1 L; W: R8 ~  o
5 5
7 G% X3 \. U/ D2 z% R) r0 1 0 0 0: A: L; z8 }8 T# f9 W4 h
0 1 0 1 0
( r: `/ j& M! H2 \7 Z/ F0 0 0 0 0( v1 {% F; O/ b8 C1 X
0 1 1 1 0# r/ y' @6 }- h, |' j
0 0 0 1 0, J  `* x3 s. p2 @2 U% a
【输出样例】
8 g5 t( p- |: `* A' h5 e8 q6 Q  [* }! a) N7 J3 l( `7 \
8
7 Y4 C0 H5 h4 O& T3 Y7 d+ U+ a 【解题思路】3 ]9 Y" S6 H' N  Q# h2 |

/ r* V+ P) u/ T2 E3 M: t        BFS的典中典。
  1. from collections import *) U& Y5 z0 e2 c% ^! k( U8 z$ i% x
  2. n,m = map(int,input().split())
    . `9 J$ b0 ?: U' R& g1 }2 q
  3. mp = [[0]*(m+5)]
    7 `% L0 }5 X( R  z  y
  4. for i in range(n):\" |) U4 {% B/ J5 i
  5.     mp.append([0]+list(map(int,input().split())))
    ) h9 b( G6 G\" k3 N* [6 z: ]7 U
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]6 \2 I- V8 s, w
  7. st = [[0]*(m+5) for _ in range(n+5)]' n3 \7 H) Q% ^\" m+ ~
  8. def bfs():
    / J! P- J0 S4 `# @5 _: I
  9.     q = deque()
    0 j* S/ Q* p. U: U! p6 u& }
  10.     q.append([1,1,0])
    , f: j; o3 y- T1 o
  11.     st[1][1]=1
    ; ^! U9 z% ~; ]! m, q0 V
  12.     while q:; |1 D% ^3 B3 O. T
  13.         tx,ty,step = q.popleft()
    0 W: n+ H& O$ I$ A, g3 p+ S
  14.         if tx==n and ty==m:: |6 Q1 @$ l0 ]; B% y7 _
  15.             print(step)
    ; N7 _- x9 S2 n, g/ S2 d: X
  16.             return
    . F8 N$ \8 ]! R' z( Q1 f1 j4 k/ T! T( q
  17.         for x_,y_ in dir:
    : H5 @0 `& g2 v$ W4 c5 O
  18.             nx,ny = tx+x_,ty+y_
    $ k0 V7 O2 _3 w6 |( h/ ?$ `$ R# Q
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    # w$ W( o$ |: l
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    ! O% o1 C: h6 q* q  z
  21.             q.append( [nx,ny,step+1] )  w6 d( z* Z- Y2 ~( c
  22.             st[nx][ny]=1* Z1 ~& T0 v0 Y8 y* I
  23. bfs()
复制代码
: B4 Z3 D$ {5 K# }7 C
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:23 , Processed in 0.417713 second(s), 51 queries .

回顶部