C++ 方格取数

试题描述：

设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

C++ 方格取数

某人从图中的左上角的A出发，可以向下行走，也可以向右行走，直到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入：

输入第一行为一个整数N（N≤10），表示N×N的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行0 0 0表示结束。

输出：

输出包含一个整数，表示两条路径上取得的最大的和。

输入示例：

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出示例：

代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
const int xx[2]={0,-1},yy[2]={-1,0};
int f[20][20][20][20],a[20][20];
int x,y,z,nx1,ny1,nx2,ny2,n;
int main()
{
	cin>>n;
	cin>>x>>y>>z;
	while(x)
	{
		a[x][y]=z;
		cin>>x>>y>>z;
	}
	for(int x1=1;x1<=n;++x1)
	for(int y1=1;y1<=n;++y1)
	for(int x2=1;x2<=n;++x2)
    for(int y2=1;y2<=n;++y2){
    	for(int i=0;i<2;++i)
    	for(int j=0;j<2;++j){
    		nx1=x1+xx[i];
    		ny1=y1+yy[i];
    		nx2=x2+xx[j];
    		ny2=y2+yy[j];
    		f[x1][y1][x2][y2]=max(f[x1][y1][x2][y2],f[nx1][ny1][nx2][ny2]);
		}
		f[x1][y1][x2][y2]=f[x1][y1][x2][y2]+a[x1][y1]+a[x2][y2];
		if(x1==x2&&y1==y2)f[x1][y1][x2][y2]-=a[x2][y2];
	}
	cout<<f[n][n][n][n];
}

四维数组，二维数组有一些麻烦。

xx和yy用于向两个方向dfs。

最后再进行一次max。

原文链接: https://www.cnblogs.com/FXY-180/p/9511755.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/279806

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++ 方格取数

相关推荐