在一个m×n棋盘中,交叉点处都放置了整数。有一个棋子,它走“目”(立“目”,不是倒“目”,走对角线),且只能向从右向左方走。开始时它可位于棋盘右方任一位置(交叉点),然后开始走棋,直至走到棋盘的最左方。用c++设计算法求出棋子经过的交叉点的数之和最大的路径、最大的和值、路径总条数,并举例输入和输出。
时间: 2024-02-21 13:01:16 浏览: 125
这是一个动态规划问题,可以使用二维数组dp[m][n]来记录到达每个位置时的最大值。其中dp[i][j]表示到达第i行第j列时,经过的交叉点的数之和的最大值。可以利用递推公式来更新dp数组。
具体来说,对于每个位置(i,j),它可以从上一行的三个位置(i-1,j-1),(i-1,j),(i-1,j+1)中的任意一个位置转移而来。因此递推公式为:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + a[i][j]
其中a[i][j]表示棋盘上第i行第j列的整数。由于棋子只能向从右向左方走,因此最终的答案就是dp[m][1],即到达最左边一列时的最大值。
在更新dp数组时,还需要记录路径总条数,可以使用另一个二维数组count[m][n]来记录。具体来说,对于每个位置(i,j),它可以从上一行的三个位置转移而来,如果有多个位置与它的值相等,则路径数要累加起来。递推公式为:
count[i][j] = 0
if dp[i][j] == dp[i-1][j-1] then count[i][j] += count[i-1][j-1]
if dp[i][j] == dp[i-1][j] then count[i][j] += count[i-1][j]
if dp[i][j] == dp[i-1][j+1] then count[i][j] += count[i-1][j+1]
if dp[i][j] == max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) then count[i][j] += 1
最后输出路径和最大值即可。
以下是完整的C++代码实现,假设棋盘大小为5x5:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int a[MAXN][MAXN], dp[MAXN][MAXN], count[MAXN][MAXN];
int main()
{
int m = 5, n = 5;
memset(dp, 0, sizeof(dp));
memset(count, 0, sizeof(count));
// 输入棋盘上的整数
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
// 递推计算dp数组和count数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j == 1) {
dp[i][j] = a[i][j];
count[i][j] = 1;
} else {
dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i-1][j+1])) + a[i][j];
if (dp[i][j] == dp[i-1][j-1]) count[i][j] += count[i-1][j-1];
if (dp[i][j] == dp[i-1][j]) count[i][j] += count[i-1][j];
if (dp[i][j] == dp[i-1][j+1]) count[i][j] += count[i-1][j+1];
}
}
}
// 输出路径和最大值,以及路径总条数
int ans = dp[m][1], paths = 0;
for (int i = 2; i <= n; i++) {
if (dp[m][i] > ans) {
ans = dp[m][i];
}
}
for (int i = 1; i <= n; i++) {
if (dp[m][i] == ans) {
paths += count[m][i];
}
}
cout << "路径和最大值:" << ans << endl;
cout << "路径总条数:" << paths << endl;
return 0;
}
```
假设输入的棋盘上的整数为:
```
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
```
则输出结果为:
```
路径和最大值:40
路径总条数:4
```
阅读全文