首页 > 试题广场 >

走迷宫

[编程题]走迷宫
  • 热度指数：15289 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个 n \times m 的网格。你从起点 (x_s, y_s) 出发，每一次可以向上、下、左、右移动一步（若不超出边界）。某些格子上存在障碍物，无法经过。求从 (x_s, y_s) 移动到终点 (x_t, y_t) 的最少步数；若无法到达，输出 -1。

输入描述:
\hspace{15pt}在一行上输入两个整数 n, m \left(1 \leqq n, m \leqq 1000\right)，代表网格的行数与列数。
\hspace{15pt}在一行上输入四个整数 x_s, y_s, x_t, y_t \left(1 \leqq x_s, x_t \leqq n;\ 1 \leqq y_s, y_t \leqq m\right)，代表起点与终点的坐标。
\hspace{15pt}此后 n 行，第 i 行输入一个长度为 m 的字符串 g_i，其中
\hspace{23pt}\bullet\,若 g_{i, j}=\texttt{，表示第 i 行第 j 列为障碍物；
\hspace{23pt}\bullet\,若 g_{i, j}=\texttt{，表示该格子可通行。
\hspace{15pt}保证起点所在格子可通行。


输出描述:
\hspace{15pt}输出一个整数，表示最少移动次数；若无法到达，输出 -1。
示例1

输入

5 5
1 1 5 5
.....
****.
.....
**.**
.....

输出

12
示例2

输入

5 5
1 1 4 5
.....
****.
.....
**.**
.....

输出

-1
示例3

输入

5 5
1 1 5 5
.....
****.
.....
*****
.....

输出

-1
算法知识视频讲解
添加回答
Python 3
牛客804244365号头像 牛客804244365号
系统默认1000次不够用，需要改多点
import sys
sys.setrecursionlimit(3000)
n , m = map(int,input().split())
res = []
mp = []
jey = []
global depth
depth = 0
def bfs(mp,edi,edj,bnow,depth,visited):
    if len(bnow) == 0:
        jey.append(0)
        return
    newb = []
    depth += 1
    for p in bnow:
        if p[0] == edi and p[1] == edj :
            jey.append(1)
            return
        di = [1,0,-1,0]
        dj = [0,1,0,-1]
        for k in range(4):
            t1 = p[0] + di[k]
            t2 = p[1] + dj[k]
            if 0 <= t1 < n and 0 <= t2 < m and mp[t1][t2] == '.' and visited[t1][t2] == 0 :
                visited[t1][t2] = 1
                newb.append((t1,t2))
    res.append(depth)
    bfs(mp,edi,edj,newb,depth,visited)

now = []    
l = list(map(int,input().split()))
sti = l[0] - 1
stj = l[1] - 1
edi = l[2] - 1
edj = l[3] - 1
now.append((sti,stj))
visted = [[0 for j in range(m)]for i in range(n)]
visted[sti][stj] = 1
for i in range(n):
    mp.append(input())
k = bfs(mp,edi,edj,now,depth,visted)
if not jey[0]:
    print('-1')
else:
    print(res[-1])
发表于 2024-12-04 18:49:45 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
难度：
1条回答 1945浏览

热门推荐

通过挑战的用户

查看代码

相关试题

走迷宫

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号