刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

迷宫问题
定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};


它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。


时间限制:1000
内存限制:65536
输入
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径,格式如样例所示。
样例输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

使用微信搜索喵呜刷题,轻松应对考试!

答案:

解析:

【喵呜刷题小喵解析】本题要求找出从左上角到右下角的最短路径,可以使用Dijkstra算法来解决。Dijkstra算法是一种用于求解最短路径问题的贪心算法,适用于权值为非负的情况。首先,我们需要初始化起点到自身的距离为0,其他点的距离初始化为无穷大,并将起点标记为已访问。然后,从未访问的点中选择距离起点最近的点,将其标记为已访问,并更新其邻居点的距离。重复这个过程,直到终点被标记为已访问。在代码实现中,我们使用一个二维数组maze来表示迷宫,其中1表示墙壁,0表示可以走的路。我们使用一个二维数组dist来记录起点到每个点的最短距离,使用一个二维数组vis来记录每个点是否被访问过。我们使用一个优先队列pq来存储待访问的点,按照距离起点的距离从小到大排序。在dijkstra函数中,我们首先初始化优先队列pq,将起点加入队列,并初始化距离数组dist和访问数组vis。然后,在循环中,从未访问的点中选择距离起点最近的点,将其标记为已访问,并更新其邻居点的距离。最后,在主函数中,我们输入迷宫,调用dijkstra函数求解最短路径,并输出路径。需要注意的是,在输出路径时,我们需要判断起点和终点是否被访问过,以及当前点是否被访问过。如果当前点是起点或终点,则直接输出坐标;否则,如果当前点没有被访问过,则跳过;否则,输出坐标并加上一个空格。最后,每行输出结束后需要换行。
创作类型:
原创

本文链接:迷宫问题 定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0,

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share