BONUS13 - VOI 2013 - Phần thưởng

Tác giả: flashmt

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstdlib>
using namespace std;
const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int k, a[10][10], E, used[10][10], flag[100];
long long ans, total; 
pair <int,int> e[100];
vector < pair<int,int> > c[10][10][4];

int inside(int x, int y)
{
	return x > 0 && y > 0 && x < 9 && y < 9;
}

void init()
{
	for (int x = 1; x <= 8; x++)
		for (int y = 1; y <= 8; y++)
		{
			for (int i = 0; i < 8; i++)
			{
				int xx = x + dx[i], yy = y + dy[i];
				if (inside(xx, yy) && a[xx][yy]) c[x][y][0].push_back(make_pair(xx, yy));
			}
			
			for (int xx = 1; xx <= 8; xx++)
			{
				int yy = x + y - xx;
				if (inside(xx, yy) && a[xx][yy]) c[x][y][1].push_back(make_pair(xx, yy));
				yy = xx + y - x;
				if (inside(xx, yy) && a[xx][yy]) c[x][y][1].push_back(make_pair(xx, yy));
			}
			
			for (int i = 1; i <= 8; i++)
			{
				if (a[i][y]) c[x][y][2].push_back(make_pair(i, y));
				if (a[x][i]) c[x][y][2].push_back(make_pair(x, i));
			}
			
			for (int z = 1; z < 3; z++)
				for (int i = 0; i < int(c[x][y][z].size()); i++)
					c[x][y][3].push_back(c[x][y][z][i]);
		}
}

void att(int z, long long score)
{
	if (z == 4)
	{
		ans = max(ans, score);
		if (ans == total)
		{
			cout << ans << endl;
			exit(0);
		}
		return;
	}
	
	for (int i = 0; i < E; i++)
		if (!flag[i])
		{
			flag[i] = 1;
			int x = e[i].first, y = e[i].second;
			for (int j = 0; j < int(c[x][y][z].size()); j++)
			{
				int xx = c[x][y][z][j].first, yy = c[x][y][z][j].second;
				if (!used[xx][yy]++) score += a[xx][yy];
			}
			
			if (z + score) att(z + 1, score);
			
			for (int j = 0; j < int(c[x][y][z].size()); j++)
			{
				int xx = c[x][y][z][j].first, yy = c[x][y][z][j].second;
				if (!--used[xx][yy]) score -= a[xx][yy];
			}
			flag[i] = 0;
		}
}

int main()
{
	int x, y, z;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> x >> y >> z;
		a[x][y] = z;
		total += z;
	}
	
	init();
	
	for (int i = 1; i <= 8; i++)
		for (int j = 1; j <= 8; j++)
			if (!a[i][j])
				e[E++] = make_pair(i, j);
	
	att(0, 0);
	
	cout << ans << endl;
}

Download