P1074 [NOIP2009 提高组] 靶形数独

题目传送门

思路

就是一个填数独的小游戏
不会填数独的先去自己玩几把
众所周知，数独每一行、每一列、每一个3*3宫格内的数字均含1~9，且不重复
所以我们设三个数组r[10][10]，c[10][10]，block[10][10]
分别记录行、列、3*3宫格内数字的使用情况
重点：剪枝
我们知道，数独的玩法是先从已知数字多的一行/一列/宫格开始填，这样要枚举的数就少，更好填
剪枝也是这个思路
记录每一行 \(0\) 的个数，然后从小到大排序再dfs，这样dfs的层数会少很多
数据比较小，所以可以只按行排就行了

然后就是最简单的搜索与回溯啦

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pc putchar
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    T f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){x=x*10+(c^48); c=getchar();}
    x*=f;
    return;
}
template<typename T,typename... Args> inline void read(T &x, Args&... args){read(x); read(args...);}
template<typename Z>
inline void write(Z x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
template<typename Z,typename... Args> inline void write(Z x, Args... args){write(x); putchar(' '); write(args...);}
const int N=10;
const int val[N][N] = {//方格分值
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 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}
};
int id(int x,int y)//看哪个宫格需要计算一下
{
    if(x<=3 && y<=3) return 1;
    if(x<=3 && y<=6) return 2;
    if(x<=3 && y<=9) return 3;
    if(x<=6 && y<=3) return 4;
    if(x<=6 && y<=6) return 5;
    if(x<=6 && y<=9) return 6;
    if(x<=9 && y<=3) return 7;
    if(x<=9 && y<=6) return 8;
    if(x<=9 && y<=9) return 9;
}
struct zer{
    int line, cnt;
    friend bool operator<(const zer& x, const zer& y){
	return x.cnt < y.cnt;
    }
}z[10];
int a[N][N];
ll ans;
bool r[N][N],c[N][N],block[N][N];//分别记录行、列、`3*3`宫格内数字的使用情况
void dfs(int pos,int x,int y)
{
    if(pos == 10)//全搜完了
    {
	ll sum = 0;
	for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
		sum += a[i][j] * val[i][j];//计算当前的数独的分数
	ans = max(ans, sum);//取最大
	return;
    }
    if(y == 10)
    {
	dfs(pos+1, z[pos+1].line, 1);//这一行填完了，递归到下一行
	return;
    }
    if(a[x][y] == 0)//这个位置没填数
    {
	for(int num=1;num<=9;num++)
	    if(!r[x][num] && !c[y][num] && !block[ id(x,y) ][num])//可以填
	    {
                r[x][num] = c[y][num] = block[ id(x,y) ][num] = 1;
		a[x][y] = num;
		dfs(pos, x, y+1);
		a[x][y] = 0;//回溯
		r[x][num] = c[y][num] = block[ id(x,y) ][num] = 0;
            }
    }
    else //这个位置填上了，去下一个数
	dfs(pos, x, y+1);
}
int main()
{
    for(int i=1;i<=9;i++)
    {
	int cnt0 = 0;
	for(int j=1;j<=9;j++)
	{
		read(a[i][j]);
		if(a[i][j] == 0) cnt0++;//一行 0 的个数
		r[i][a[i][j]] = 1;
		c[j][a[i][j]] = 1;
		block[ id(i,j) ][a[i][j]] = 1;
	}
	z[i] = {i, cnt0};
    }
    sort(z+1, z+10);//根据 0 的数量排序
    dfs(1, z[1].line, 1);
    write(ans);
    return 0;
}