使用C++实现在m行n列的棋盘,交叉点处都放置了整数,棋盘上有一个棋子它走“日”(立“日”,不是倒“日”,走对角线),且只能从左向右走。可从最左边的任一位置开始走。设计算法求出棋子经过的交叉点的数之和最小的路径、最小的和值、路径总条数。 C++实现
时间: 2023-12-10 11:39:07 浏览: 100
这是一个比较经典的动态规划问题,可以使用二维数组来存储每个位置的最小和值,以及从左上角到该位置的路径总条数。
具体实现步骤如下:
1. 定义一个二维数组 dp,其中 dp[i][j] 表示从左侧开始走到坐标为 (i,j) 的位置的最小和值。
2. 初始化 dp 数组的第一列,即 dp[i][0] = grid[i][0],因为从左侧开始走,只能一直往右走。
3. 对于每个位置 (i,j),计算出它的最小和值:
dp[i][j] = min(dp[i-1][j-2], dp[i-2][j-1]) + grid[i][j]
其中,dp[i-1][j-2] 表示从 (i-1,j-2) 位置走过来的最小和值,dp[i-2][j-1] 表示从 (i-2,j-1) 位置走过来的最小和值,取它们之间的较小值,再加上当前位置的值 grid[i][j]。
4. 最后,dp[m-1][n-1] 就是从左侧开始走到右下角的位置的最小和值,路径总条数也可以在计算 dp 数组的过程中同时求出。
C++代码如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
// 初始化棋盘
vector<vector<int>> grid(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
// 计算最小和值和路径总条数
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i-1][j-2], dp[i-2][j-1]) + grid[i][j];
}
}
cout << "最小和值:" << dp[m-1][n-1] << endl;
cout << "路径总条数:" << dp[m-1][n-1] << endl;
return 0;
}
```
阅读全文