洛谷1074 靶形数独

原题链接

终究还是逃不过这题，真的懒得写爆搜。。

在某一行中填数时，可以使用链表以减少无用的遍历，即防止遍历到在该行已经填过的数字。
再开\(3\)个数组，一个记录改格是否填过数，一个记录这一列中哪些数已经存在，一个记录这个格子所在的九宫格里哪些数已经存在。
对于转成九宫格的下标，其实是有公式的，不过我比较懒，就直接用\(if\)判断了。
在搜到的格子分数相对较小的情况下，从小到大填数，相对较大则从大到小填。
而一个比较好优化就是先搜未知量少的行，能有效减少搜索树的枝叶。
另外，这题可以用二进制优化的数独，效率比单纯的爆搜要高，但我太菜了，不会。

#include<cstdio> #include<algorithm> using namespace std; const int N = 11; struct lt {	int pre, suc; }; lt H[N][N]; struct dd {	int id, s; }; dd nz[N]; bool v[N][N], vl[N][N], vg[4][4][N]; int a[N][N] = {	{0},	{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},	{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},	{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},	{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},	{0, 6, 7, 8, 9, 10, 9, 8, 7, 6},	{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},	{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},	{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},	{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}, }, ans, s; inline int re() {	int x = 0;	char c = getchar();	bool p = 0;	for (; c < '0' || c > '9'; c = getchar())	p |= c == '-';	for (; c >= '0' && c <= '9'; c = getchar())	x = x * 10 + c - '0';	return p ? -x : x; } void dfs(int x, int y); inline int maxn(int x, int y) { return x > y ? x : y; } inline void del(int x, int y) { H[x][H[x][y].pre].suc = H[x][y].suc; H[x][H[x][y].suc].pre = H[x][y].pre; }//删除链表中的某个链节 inline void rec(int x, int y) { H[x][H[x][y].pre].suc = y; H[x][H[x][y].suc].pre = y; }//恢复链表中的某个链节 inline int ch(int x) { return x < 4 ? 1 : x > 6 ? 3 : 2; }//转为就九宫格的下标 bool comp(dd x, dd y) { return x.s > y.s; } void calc(int x, int y, int i, int xx) {	if (vl[y][i] || vg[ch(x)][ch(y)][i])	return;	v[x][y] = vl[y][i] = vg[ch(x)][ch(y)][i] = 1;	del(x, i);	s += i * a[x][y];	dfs(xx, y + 1);	s -= i * a[x][y];	rec(x, i);	v[x][y] = vl[y][i] = vg[ch(x)][ch(y)][i] = 0; } void dfs(int xx, int y) {	if (y > 9)	++xx, y = 1;	int i, x = nz[xx].id;	if (x > 9)	{	ans = maxn(ans, s);	return;	}	if (v[x][y])	{	dfs(xx, y + 1);	return;	}	if (a[x][y] < 9)//格子分数相对较小的情况下，从小到大填数	for (i = H[x][0].suc; i <= 9; i = H[x][i].suc)	calc(x, y, i, xx);	else//否则从大到小填	for (i = H[x][10].pre; i; i = H[x][i].pre)	calc(x, y, i, xx); } int main() {	int i, j, x;	for (i = 1; i <= 9; i++)	for (j = H[i][0].suc = 1, H[i][10].pre = 9; j <= 9; j++)	H[i][j].pre = j - 1, H[i][j].suc = j + 1;//初始化链表	for (i = 1, nz[10].id = 10; i <= 9; i++)	for (j = 1, nz[i].id = i; j <= 9; j++)	{	x = re();	if (!x)	continue;	nz[i].s++;	s += x * a[i][j];	del(i, x);	if (vl[j][x] || vg[ch(i)][ch(j)][x])//如果输入的数独就不合法，直接输出-1	return printf("-1"), 0;	v[i][j] = vl[j][x] = vg[ch(i)][ch(j)][x] = 1;	}	sort(nz + 1, nz + 10, comp);//按未知量的多少对行的搜索顺序进行排序	dfs(1, 1);	printf("%d", ans ? ans : -1);	return 0; }