一个3*3的地图,只能向上走或者向右走,现在要从左下角走到右上角,输入每条路的权值,输出最短路径的距离
时间: 2024-03-21 18:44:40 浏览: 13
这道题目可以使用动态规划算法来解决。
我们可以使用一个二维数组dp[i][j]来表示从起点(0,0)到点(i,j)的最短路径长度。则有状态转移方程:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + weight[i][j]
其中,weight[i][j]表示点(i,j)的权值,即从该点到达终点的距离。边界条件是dp[0][0] = weight[0][0],dp[i][0] = dp[i-1][0] + weight[i][0],dp[0][j] = dp[0][j-1] + weight[0][j]。
最终答案即为dp[2][2](因为题目中给定的是一个3*3的地图,右上角的坐标为(2,2))。
代码如下:
```c++
#include <iostream>
#include <climits>
using namespace std;
int weight[3][3]; // 存储每条路的权值,需要手动输入
int main() {
// 读入每条路的权值
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> weight[i][j];
}
}
int dp[3][3]; // 定义动态规划数组
dp[0][0] = weight[0][0]; // 边界条件
for (int i = 1; i < 3; i++) {
dp[i][0] = dp[i-1][0] + weight[i][0];
dp[0][i] = dp[0][i-1] + weight[0][i];
}
for (int i = 1; i < 3; i++) {
for (int j = 1; j < 3; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + weight[i][j];
}
}
cout << dp[2][2] << endl; // 输出最短路径长度
return 0;
}
```
需要注意的是,这个算法的时间复杂度是O(n^2),因为需要遍历整个3*3的地图。当地图规模变大时,我们需要使用更加高效的算法来解决这个问题。