数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】/ b# a' I! ?: v5 V0 r

# B$ z- s( u" N: Z. b& R        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
9 i& `1 k9 {3 n0 o# J: m
8 H  _( s% `* A, I【输入格式】3 u" K. K( @4 t$ H
& L; [' q; A2 `+ {  _* e1 M' q4 `
        第一行包含两个整数 n 和 m。
1 t) \$ O) X1 e& R  G' w& T1 B" L0 {4 i2 ?6 D# T0 w$ F/ ]
        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。2 U) Z+ o: C+ ^5 [4 N0 h

* P8 `/ m9 s4 @- L9 i! S# q【输出格式】
5 v6 z# G" c+ g( f
( U; M; Z9 U) R8 W$ k: ?; v        输出一个整数，表示从左上角移动至右下角的最少移动次数。, l1 D/ Y- g3 z

% r) F1 ^  i3 r% L  J/ I! X. c- W【数据范围】
* W; k1 E: l, b% A, R0 x# X! G0 T9 c3 N' ?+ q8 A6 ]
        1≤n,m≤1006 _) r9 f: d2 |9 T; s6 D- K
$ d+ s9 x9 @9 ]% t$ H7 D9 Y/ f5 L
【输入样例】
6 |0 O/ E) A: Y8 x9 @! u! K0 ?) {
9 |  o) G6 T4 Z' i+ Q* E5 5- `& X- @; G; B$ A# g0 X
0 1 0 0 0# F" q0 L2 Y# w  u) p6 T
0 1 0 1 0, n: b4 V5 ]+ |4 |& Q% N  l
0 0 0 0 0
, W9 P- r, u0 E' q+ [  Y0 1 1 1 0
% x: P- _4 V- y) L0 0 0 1 0
! q+ v& w& v# ~( F【输出样例】% G8 w# w! H. ^* }

+ H# k3 N: a. o8 I8% A# o  b5 W3 ?
【解题思路】  N9 B1 G! E) r9 [0 A/ H9 Y
8 I5 u! t9 |: n! l0 Y. L% I
        BFS的典中典。
  1. from collections import ** U& A; P4 y+ C4 J% I! }
  2. n,m = map(int,input().split())
    % K8 C' p$ ^: T& o, @/ t
  3. mp = [[0]*(m+5)]4 C! v, f5 N; C. y, x! w
  4. for i in range(n):4 v1 B' i; e& A; ?* N4 b
  5.     mp.append([0]+list(map(int,input().split())))8 z0 }0 P3 ~, t0 Z- X
  6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
    ) h" ?8 ~# a6 v
  7. st = [[0]*(m+5) for _ in range(n+5)]! R9 p6 w$ z2 e# v# v
  8. def bfs():# l1 |& E5 n' L8 K( p0 ~) l
  9.     q = deque()" I' a: C# `* X. ~# C7 d
  10.     q.append([1,1,0])8 u  @( Y1 O, D( q2 G
  11.     st[1][1]=1- p1 P- j) ?4 _  L9 t
  12.     while q:6 j0 v( M6 c3 K1 T9 `& @  ]
  13.         tx,ty,step = q.popleft()2 i1 H: e: ^3 o) |4 h9 n4 ]6 J4 W
  14.         if tx==n and ty==m:6 w# x8 E4 O% x* U9 s
  15.             print(step)& z8 U7 A" z8 f' l1 R  f% E
  16.             return
    2 F# ^" n) H8 J- \) H1 H$ J
  17.         for x_,y_ in dir:  g* i- t+ z! u. V; X+ }0 j; Z
  18.             nx,ny = tx+x_,ty+y_
      X8 D. C8 Y1 L" y. }
  19.             if nx<1 or nx>n or ny<1 or ny>m:continue; J9 }! x! m7 H# O) B+ L! F# o  G# {
  20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    % s# e0 ^! T' j: M" {; o" P
  21.             q.append( [nx,ny,step+1] )
    9 p8 O: j+ u8 I
  22.             st[nx][ny]=1
    $ X! E; r3 Z0 \. V" \9 c+ R: d
  23. bfs()
复制代码
# B3 R) i* h; C% y6 B




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