请用c++代码实现:一个机器人位于一个 m x n 迷宫的左上角 ,迷宫中每个格子中有距离数值,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角的最小距离和最短路径
时间: 2024-06-02 14:14:25 浏览: 93
//假设迷宫地图为二维数组maze,m为行数,n为列数
int minDist(int** maze, int m, int n) {
int dp[m][n]; //dp[i][j]表示从起点到maze[i][j]的最小距离
dp[0][0] = maze[0][0]; //起点的最小距离为起点的权值
//初始化边界
for(int i=1; i<m; i++)
dp[i][0] = dp[i-1][0] + maze[i][0];
for(int j=1; j<n; j++)
dp[0][j] = dp[0][j-1] + maze[0][j];
//递推计算dp数组
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + maze[i][j];
}
}
return dp[m-1][n-1]; //返回终点的最小距离
}
//求最短路径
void shortestPath(int** maze, int m, int n, int* path, int* len) {
int dp[m][n]; //dp[i][j]表示从起点到maze[i][j]的最小距离
dp[0][0] = maze[0][0]; //起点的最小距离为起点的权值
//初始化边界
for(int i=1; i<m; i++)
dp[i][0] = dp[i-1][0] + maze[i][0];
for(int j=1; j<n; j++)
dp[0][j] = dp[0][j-1] + maze[0][j];
//递推计算dp数组
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + maze[i][j];
}
}
//回溯求最短路径
int i = m-1, j = n-1, k = 0;
while(i != 0 || j != 0) {
path[k++] = i*n + j;
if(i == 0) j--;
else if(j == 0) i--;
else {
if(dp[i-1][j] < dp[i][j-1]) i--;
else j--;
}
}
path[k++] = 0;
*len = k;
//将路径反转
for(int i=0; i<k/2; i++) {
int temp = path[i];
path[i] = path[k-i-1];
path[k-i-1] = temp;
}
}
阅读全文