看本题发题解的人比较少，水一发。

这道题比较考验搜索，但主要还是考验代码能力。

这里就按y总的讲了。

1. 先搜行列里确定多的
2. 先搜数多的

这里可以用lowbit运算加上预处理幂，用二进制优化的方法来进行剪枝。（一道中等题肯定不是随随便便就能过的

总体思路就是这样，贴代码。

再剩下的看注释吧

#include<bits/stdc++.h>
using namespace std;
const int N = 9;
int ones[1 << N], Log[1 << N];//因为是和2进制有关的，存幂和1，需要开1 << N
int row[N], col[N], cell[5][5];//行列和九宫格
int g[N][N];//存整个图
int ans = -1;//防止最后特判
inline int lowbit(int x)
{
    return x & -x;//lowbit运算，二进制优化
}
void init()
{
    for(int i = 0; i < N; i ++) Log[1 << i]  = i;//把所有的幂初始化
    for(int i = 0; i < (1 << N); i ++)
        for(int j = i; j; j -= lowbit(j))
            ones[i] ++;//算出lowbit，预处理提高运行效率
    for(int i = 0; i < N; i ++) row[i] = col[i] = cell[i / 3][i % 3] = (1 << N) - 1;//初始化3个记录

}
inline int get_scorl(int x, int y)
{
    return min(min(x, 8 - x), min(y, 8 - y)) + 6;//看题目
}
inline void drow(int x, int y, int t)
{
    int s = 1;
    if(t > 0)
    {
        g[x][y] = t;//若t有数直接记录
    }
    else s = -1, t = -t, g[x][y] = 0;//否则先讲t取反，然后需要将s变成-1方便后续改变整个数独的二进制
    t --;
    //改变二进制
    row[x] -= s << t;
    col[y] -= s << t;
    cell[x / 3][y / 3] -= s << t;
}
inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];//这个是需要返回对应的位置
}
inline void dfs(int cnt, int scorl)//最重要的dfs
{
    if(!cnt) 
    {
        ans = max(ans, scorl);//如果没有空格直接return
        return ;
    }
    int x, y;
    int mins = 10000;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            if(!g[i][j])
            {
                int state = get(i, j);//get出来
                if(ones[state] < mins)
                {
                    mins = ones[state];//更新最小
                    x = i, y = j;
                }
            }
    //对最小进行爆搜
    for(int i = get(x, y); i ; i -= lowbit(i))
    {
        int t = Log[lowbit(i)] + 1;
        drow(x, y, t);
        dfs(cnt - 1, scorl + get_scorl(x, y) * t);
        drow(x, y, -t);//不要忘记回溯（
    }
}
int main()
{
    init();
    int cnt = 0;
    int scorl = 0;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
        {
            int x;
            cin >> x;
            if(x > 0)
            {
                drow(i, j, x);//这些东西没啥好说的，算分值，把输入画进g数组
                scorl += x * get_scorl(i, j);
            }
            else cnt ++;
        }
    dfs(cnt, scorl);
    cout << ans << endl;
    return 0;
}

毒瘤死了

下一篇题解更新上一行的题目（