WA #3 #5

#include<bits/stdc++.h>
using namespace std;
int n;
int ditu[12][12];
bool mem[12][12][3][10000];//记忆化搜索
int ans;
void dfs(int x, int y, int k, int sum)
{
	if (mem[x][y][k][sum] || x > n || y > n)
	{
		return;
	}
	mem[x][y][k][sum] = true;
	if (k == 2)
	{
		ans = max(ans, sum);
		return;
	}
	sum += ditu[x][y];
	int p = ditu[x][y];
	ditu[x][y] = 0;
	if (x == n && y == n)
	{
		k++;
		x = 1;
		y = 1;
	}
	dfs(x + 1, y, k, sum);
	dfs(x, y + 1, k, sum);
	ditu[x][y] = p;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	while (true)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 0 && b == 0 && c == 0)
		{
			break;
		}
		ditu[a][b] = c;	
	}
	dfs(1, 1, 0, 0);
	cout << ans << endl;
	return 0;
}