数学建模社区-数学中国

标题: python 走迷宫问题 [打印本页]

---

作者: 2744557306    时间: 2024-3-20 11:40
标题: python 走迷宫问题
题目描述】

% @1 ~, j( {4 m9 @  C: p" r        给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

4 @6 V' J* e  O# h【输入格式】
2 A( ?$ G+ L( M8 [1 h1 h* q4 ^2 T
        第一行包含两个整数 n 和 m。

/ i& e. X$ o/ j6 |3 V6 k" R        接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

【输出格式】
* A# @: w9 S3 I& \/ R. L, Y/ n
        输出一个整数，表示从左上角移动至右下角的最少移动次数。

& ^3 W) p7 L% I【数据范围】
# l* g9 L: |0 X" ^% o5 S. o
        1≤n,m≤100
" q' c* q) s$ l' H0 F
【输入样例】

$ {6 o9 I, U( a. W5 5
* N! }3 D8 g4 v% J0 m4 Y0 1 0 0 0
0 1 0 1 0
2 b* K& P4 \& H& W* P/ D' U5 G0 0 0 0 0
0 1 1 1 0
  W0 E# @& f9 [* E) _9 Y* r0 v3 U0 0 0 1 0
【输出样例】
& S- G/ M# l& K
8
【解题思路】

& S; D% v  d, F        BFS的典中典。

1. from collections import *
   ' `1 ^3 |1 @4 V* N: e3 k: o
2. n,m = map(int,input().split())
   
3. mp = [[0]*(m+5)]
   
4. for i in range(n):
   0 P) s5 c4 a) ~- P& U5 D0 V
5.     mp.append([0]+list(map(int,input().split())))
   + x& e0 l" |/ M4 D! z
6. dir = [(1,0),(-1,0),(0,1),(0,-1)]
   ( c0 G5 a% H7 [: W
7. st = [[0]*(m+5) for _ in range(n+5)]
   3 U1 F8 a9 D+ N! v6 `
8. def bfs():
   
9.     q = deque()
   
10.     q.append([1,1,0])
    7 c! o+ `# T, ^# y7 s( t8 G
11.     st[1][1]=1
    
12.     while q:
    
13.         tx,ty,step = q.popleft()
    
14.         if tx==n and ty==m:
      s$ }# [$ [! r% M( N: A  T1 T" ]. L
15.             print(step)
    
16.             return
    
17.         for x_,y_ in dir:
    5 @4 V5 J% f: t
18.             nx,ny = tx+x_,ty+y_
    
19.             if nx<1 or nx>n or ny<1 or ny>m:continue
    
20.             if mp[nx][ny]==1 or st[nx][ny]:continue
    
21.             q.append( [nx,ny,step+1] )
    
22.             st[nx][ny]=1
    & K9 P5 q# Y- b* Q) i
23. bfs()

复制代码

. n! m& H  p) u% t* o, U% G  ^, V

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5