给定一个m*n大小的矩阵T,对于其中的每个位置(i,j),有T[i,j] >=—1:如果T[i,j] =—1则表示该位置为墙;如果T[i,j] >=0为则表示该位置为空,但该位置的权值为T[i,j]。 坐标(1,1)为起点S,坐标(m,n)的位置为终点T(默认这两个位置的元素为0)。请设计一个程序,若该迷宫存在一条路径连接S和T(即该路径所经过的位置的权值皆>=0):则返回连接S和T的一条“最短”路径;否则返回“无”。注意一条连接S和T的路径的“长度”定义为它所走过的位置的权值之和。连接S和T的“最短”路径是指在所有连接S和T的路径当中,长度最小的那一条。注意在走该迷宫时,每次只能选择“上下左右”四个方向中的一个进行移动。如果将要移动的位置有墙,则待在原地。可先基于迷宫构造相应的无向图,再利用Dijkstra算法的思路进行求解。注意这个问题不能直接利用Dijkstra算法进行求解。声明:本文仅代表作者观点,不代表本站立场。如果侵犯到您的合法权益,请联系我们删除侵权资源!如果遇到资源链接失效,请您通过评论或工单的方式通知管理员。未经允许,不得转载,本站所有资源文章禁止商业使用运营!

下载安装【程序员客栈】APP
实时对接需求、及时收发消息、丰富的开放项目需求、随时随地查看项目状态
评论