【算法分析与设计】双胞胎探宝
2024-01-02 09:18:39
问题描述:
现有一对双胞胎,在一个有n * n个方格的方形宝藏区域F中探宝。(i,j)方格中宝物的价值为v(i,j),如下图所示。
A
3 2
5
7 1
9 B
双胞胎均从F的A点出发,向下或向右行走,直到B点,在走过的路上,收集方格中的宝藏。试找出兄弟二人可以获得的宝藏总价的值最大。
数据输入:
输入数据第1行有1个正整数n,表示方形区域F有n * n个方格。 接下来每行有3个整数,前2个表示方格位置,第3个数为该位置宝藏价值。最后一行是3个0。
样例输入:
8 2 2 3 2 5 2 3 4 5 4 1 7 4 3 1 5 2 9 0 0 0
样例输出:
24
代码:
#include <stdio.h>
#define MAXN 100
int n; // 方形区域边长
int g[MAXN][MAXN]; // 样本(宝物)价值
int h[MAXN][MAXN][MAXN][MAXN]; // 记录路径的最大样本价值
void val(int x1, int y1, int x2, int y2, int v);
void dyna();
int main()
{
scanf("%d", &n); // 输入方形区域边长,n*n 方格
// 输入样本价值
int x, y, v;
while (1)
{
scanf("%d %d %d", &x, &y, &v);
if (x == 0 && y == 0 && v == 0)
{
break;
}
g[x][y] = v;
}
dyna(); // 求解最大样本价值
// 输出最大样本价值
printf("%d\n", h[n][n][n][n]);
return 0;
}
void val(int x1, int y1, int x2, int y2, int v)
{
if (x1 == x2 && y1 == y2)
{
h[x1][y1][x2][y2] = h[x1][y1][x2][y2] > v + g[x1][y1] ? h[x1][y1][x2][y2] : v + g[x1][y1];
}
else
{
h[x1][y1][x2][y2] = h[x1][y1][x2][y2] > v + g[x1][y1] + g[x2][y2] ? h[x1][y1][x2][y2] : v + g[x1][y1] + g[x2][y2];
}
}
void dyna()
{
int x1, y1, x2, y2, s, v;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
for (int l = 0; l <= n; l++)
{
h[i][j][k][l] = 0;
}
}
}
}
h[1][1][1][1] = g[1][1];
for (s = 2; s <= n + n - 1; s++)
{
for (x1 = 1; x1 <= s - 1; x1++)
{
for (x2 = 1; x2 <= s - 1; x2++)
{
y1 = s - x1;
y2 = s - x2;
v = h[x1][y1][x2][y2];
val(x1 + 1, y1, x2 + 1, y2, v);
val(x1 + 1, y1, x2, y2 + 1, v);
val(x1, y1 + 1, x2 + 1, y2, v);
val(x1, y1 + 1, x2, y2 + 1, v);
}
}
}
}
文章来源:https://blog.csdn.net/Walker501/article/details/135298671
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!