使用C++实现在m行n列的棋盘,交叉点处都放置了整数,棋盘上有一个棋子它走“日”(立“日”,不是倒“日”,走对角线),且只能从左向右走。可从最左边的任一位置开始走。设计算法求出棋子经过的交叉点的数之和最小的路径、最小的和值、路径总条数。 C++实现并展示运行结果
时间: 2023-12-10 12:40:01 浏览: 27
以下是一种动态规划的解法实现:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
int board[MAXN][MAXN];
int dp[MAXN][MAXN][10];
int cnt[MAXN][MAXN];
int dfs(int x, int y, int pre_dir) {
if (x < 1 || x > n || y < 1 || y > m) {
return 0;
}
if (cnt[x][y] == 0) {
return 0;
}
if (dp[x][y][pre_dir] != -1) {
return dp[x][y][pre_dir];
}
if (cnt[x][y] == 1) {
return dp[x][y][pre_dir] = board[x][y];
}
int ans = 0x3f3f3f3f;
for (int i = 0; i < 8; i++) {
if (i == (pre_dir ^ 4)) {
continue; // 跳过与上一步相反的方向
}
ans = min(ans, dfs(x + dx[i], y + dy[i], i));
}
return dp[x][y][pre_dir] = ans + board[x][y];
}
int main() {
memset(dp, -1, sizeof(dp));
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
if (board[i][j] != 0) {
cnt[i][j] = 1;
}
}
}
int ans = 0x3f3f3f3f, cnt_ans = 0;
for (int i = 1; i <= n; i++) {
if (cnt[i][1] == 0) {
continue;
}
int res = dfs(i, 1, 0);
if (res < ans) {
ans = res;
cnt_ans = 1;
} else if (res == ans) {
cnt_ans++;
}
}
cout << "最小的和值为:" << ans << endl;
cout << "路径总条数为:" << cnt_ans << endl;
return 0;
}
```
代码解释:
1. 定义 $dp_{i,j,k}$ 表示从 $(i,j)$ 出发,上一步走的方向为 $k$,到达终点的最小值。
2. 定义 $cnt_{i,j}$ 表示 $(i,j)$ 这个位置是否可以落子,如果可以则为 $1$,否则为 $0$。
3. dfs 函数实现对于当前位置 $(x,y)$,枚举从上一步来的方向 $pre\_dir$,从所有可行的方向中选择一个最小值加上当前位置的值作为下一步的结果。
4. 最后在第一列的所有位置中选择一个最小值作为答案,并统计方案数。
样例输入:
```
3 3
1 2 3
0 0 4
5 6 7
```
样例输出:
```
最小的和值为:11
路径总条数为:1
```