【NOIP 2009】 靶形数独

【题目链接】

            https://www.luogu.org/problemnew/show/P1074

【算法】

            搜索 + 剪枝

【代码】

           

#include<bits/stdc++.h>
using namespace std;
const int INF = 2e9;

struct point
{
        int x,y;
} a[100];

int i,j,ans,n,Mask,t;
int val[9][9];
int w[2000],num[2000];
bool used[100];
int row[10],col[10],grid[10];
bool solved;

const int s[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}
};

inline int lowbit(int x)
{
        return x & (-x);
}
inline void chkmax()
{
        int i,ret = 0;
        for (i = 0; i < 9; i++)
        {
                for (j = 0; j < 9; j++)
                {
                        ret += val[i][j] * s[i][j];
                }
        }
        ans = max(ans,ret);
}
inline void dfs(int dep)
{
        int i,mn,pos,v,t;
        if (dep > n)
        {    
                solved = true;
                chkmax();
                return;
        }    else
        {
                v = 0; mn = INF;
                for (i = 1; i <= n; i++)
                {
                        if (!used[i])
                        {
                                t = row[a[i].x] & col[a[i].y] & grid[a[i].x/3*3+a[i].y/3];
                                if (!t) continue;
                                if (w[t] < mn) 
                                {
                                        mn = w[t];
                                        pos = i;
                                        v = t;
                                }
                        }
                }
                while (v)
                {
                        used[pos] = true;
                        val[a[pos].x][a[pos].y] = num[lowbit(v)] + 1;
                        row[a[pos].x] ^= lowbit(v);
                        col[a[pos].y] ^= lowbit(v);
                        grid[a[pos].x/3*3+a[pos].y/3] ^= lowbit(v);
                        dfs(dep+1);
                        used[pos] = false;
                        row[a[pos].x] ^= lowbit(v);
                        col[a[pos].y] ^= lowbit(v);
                        grid[a[pos].x/3*3+a[pos].y/3] ^= lowbit(v);
                        val[a[pos].x][a[pos].y] = 0;
                        v -= lowbit(v);                
                }
        }
}

int main() 
{
        
        Mask = (1 << 9) - 1;
        for (i = 0; i <= Mask; i++)
        {
                w[i] = 0;
                t = i;
                while (t)
                {
                        w[i]++;
                        t -= lowbit(t);
                }
        }
        for (i = 0; i < 9; i++) num[1 << i] = i;
        for (i = 0; i < 9; i++) row[i] = col[i] = grid[i] = Mask;
        for (i = 0; i < 9; i++)
        {
                for (j = 0; j < 9; j++)
                {
                        scanf("%d",&val[i][j]);
                        if (!val[i][j]) 
                        {
                                n++;
                                a[n] = (point){i,j};
                        } else 
                        {
                                row[i] ^= (1 << (val[i][j] - 1));
                                col[j] ^= (1 << (val[i][j] - 1));
                                grid[i/3*3+j/3] ^= (1 << (val[i][j] - 1));        
                        } 
                }
        }
        solved = false;
        dfs(1);
        if (solved) printf("%d
",ans);
        else printf("-1
");
        
        return 0;
    
}