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;
}