数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】
: N1 @0 v/ L( }. ~& {
; N6 C. y* U9 M        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。4 m* E3 Z' x) z& B9 H, w
7 V/ ]& p! A" G4 j$ I* }; }/ o
【输入格式】. B8 j& G5 T* f- I1 T

! ]. R2 s- V3 q; ^+ }        第一行包含两个整数 n 和 m。
9 t) P; J# I/ B. D) x' r$ |& J
/ P# }: ^" [+ G$ w3 r6 T        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
: [( A- P2 e* z! }8 ~; I; x# s% D! P1 ]% R( s
【输出格式】) N7 h  o3 ]1 {, e8 j' _

; h7 e7 i) |, q8 X0 t3 j        输出一个整数，表示从左上角移动至右下角的最少移动次数。
/ F9 x6 X/ D0 S7 n6 B( }
  ^1 u. v, ~3 P9 n/ l【数据范围】
( r( V/ L, D* k  a* D/ Y7 L9 M+ a  e) w* z9 g1 b" K8 x
        1≤n,m≤100
1 ?8 F# p; i, J( K2 ]
7 N1 h" |* G$ Q8 z【输入样例】
( }+ l8 ^& Z- b; ?1 J% H
. J; F6 u0 z) a3 H  b5 54 u. B& y; g+ }6 h) h
0 1 0 0 0
: n5 A, v. i5 U4 {0 1 0 1 0
5 A- n( W8 t( C4 P0 \" L0 0 0 0 0" u9 U6 n* P) u# p7 k
0 1 1 1 0) f+ ]5 r5 G$ \- F- Y  V9 Q
0 0 0 1 0, b) ^+ h- x- V! v
【输出样例】  t* a$ y- c" Z* R. b% X& w

2 o# ~. j0 T8 J. W- B, u8
+ I$ h( n9 ^. a0 f# j 【解题思路】/ G6 E. `8 ?% \: b" u/ i( H: F

0 Y4 k+ O, l; y& h3 N        BFS的典中典。
  1. from collections import *
    ( W8 l$ ]% h* C, u* K
  2. n,m = map(int,input().split())
    0 i" s: H2 I  }' P/ ]
  3. mp = [[0]*(m+5)]
    8 r1 w* ^' l+ I: L; ~# I5 |. T
  4. for i in range(n):) H( Z% ~4 X; H: N: j) \
  5.     mp.append([0]+list(map(int,input().split())))
    7 w5 r1 |$ _; @9 ^$ G0 x
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]8 [, H* q4 f( o; C, z, k
  7. st = [[0]*(m+5) for _ in range(n+5)]4 o0 Y( b& q9 @2 h; p
  8. def bfs():
    + ]5 \* `$ L$ Y4 A; L) x
  9.     q = deque()
    % F4 k# E5 I: h8 d
  10.     q.append([1,1,0])4 a7 f8 b( u) e/ S/ o" v
  11.     st[1][1]=17 v: c" Y4 ^6 @; B: Y% I
  12.     while q:# O0 H! }/ \: z  h$ J2 }( J9 k* p  ^3 k
  13.         tx,ty,step = q.popleft()
    6 _7 N$ r  m- ^& v: b8 {
  14.         if tx==n and ty==m:1 |! y$ W0 o* l4 y8 E6 E. ~
  15.             print(step)
    0 C; ]2 ]  @" b
  16.             return8 g/ ^7 J2 z0 k$ `
  17.         for x_,y_ in dir:  t  u9 l3 i1 A4 m
  18.             nx,ny = tx+x_,ty+y_
    5 w+ V3 w& ^" `7 C* x; z
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue# _, f! s* B7 z# v+ P
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    8 }- H9 c! |- |0 j
  21.             q.append( [nx,ny,step+1] )
    - @0 j- Y, D& k+ J. S
  22.             st[nx][ny]=1
    6 h: C9 W! g4 [* b% ]; }
  23. bfs()
复制代码

6 I# g1 o& k1 Q) S3 g" D! t



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5