TLE #8 #10 #13 求捞

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 750, M = 350;
int val[9][9] = {
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6},
};
int maxv = 0;
int u[N * M], l[N * M], r[N * M], d[N * M];
int h[N], s[M];
int row[N * M], col[N * M];
int m = 324, cnt;
int ans[9][9];
bool flag = 0;
void init()
{
	for (int i = 0; i <= m; i++) {
		l[i] = i - 1, r[i] = i + 1;
		u[i] = d[i] = i;
	}
	l[0] = m, r[m] = 0, cnt = m;
}
void link(int x, int y)
{
	row[++cnt] = x, col[cnt] = y, s[y]++;
	u[cnt] = u[y];
	d[u[y]] = cnt;
	d[cnt] = y;
	u[y] = cnt;
	if (!h[x])h[x] = l[cnt] = r[cnt] = cnt;
	else
	{
		l[cnt] = l[h[x]];
		r[l[h[x]]] = cnt;
		r[cnt] = h[x];
		l[h[x]] = cnt;
	}
}
void remove(int y)
{
	r[l[y]] = r[y], l[r[y]] = l[y];
	for (int i = d[y]; i != y; i = d[i])
		for (int j = r[i]; j != i; j = r[j])
			u[d[j]] = u[j], d[u[j]] = d[j], s[col[j]]--;
}
void resume(int y)
{
	r[l[y]] = l[r[y]] = y;
	for (int i = d[y]; i != y; i = d[i])
		for (int j = r[i]; j != i; j = r[j])
			u[d[j]] = d[u[j]] = j, s[col[j]]++;
}
void dance(int idx)
{
	if (r[0] == 0)
	{
		flag = 1;
		int res = 0;
		for (int i = 0; i <= 8; i++)
			for (int j = 0; j <= 8; j++)
				res += ans[i][j] * val[i][j];
		maxv = max(maxv, res);
		return;
	}
	int y = r[0];
	for (int i = r[0]; i; i = r[i])
		if (s[y] > s[i])y = i;
	remove(y);
	for (int i = d[y]; i != y; i = d[i])
	{
		int a = (row[i] - 1) / 81, b = (row[i] - 1) % 81 / 9, v = (row[i] - 1) % 9 + 1;
		ans[a][b] = v;
		for (int j = r[i]; j != i; j = r[j])remove(col[j]);
		dance(idx + 1);
		for (int j = r[i]; j != i; j = r[j])resume(col[j]);
		ans[a][b] = 0;
	}
	resume(y);
}
int main()
{
	init();
	for (int i = 0; i <= 8; i++)
		for (int j = 0; j <= 8; j++)
		{
			int x;
			scanf("%d", &x);
			for (int k = 1; k <= 9; k++)
			{
				if (x == 0 || x == k)
				{
					int t = i * 81 + j * 9 + k;
					link(t, i * 9 + j + 1);
					link(t, 81 + i * 9 + k);
					link(t, 162 + j * 9 + k);
					link(t, 243 + (i / 3 * 3 + j / 3) * 9 + k);
				}
			}
		}
	dance(0);
	if (!flag)puts("-1");
	else printf("%d\n", maxv);
	return 0;
}