P1074 靶形数独-白红宇

P1074 靶形数独

阅读量：5285 次

发布时间：2019-06-14

本文共 3645 字，大约阅读时间需要 12 分钟。

比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

输入输出格式

输入格式：

一共

输出格式：

输出共

输入输出样例

输入样例#1：

7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2

输出样例#1：

输入样例#2：

0 0 0 7 0 2 4 5 3 9 0 0 0 0 8 0 0 0 7 4 0 0 0 5 0 1 0 1 9 5 0 8 0 0 0 0 0 7 0 0 0 0 0 2 5 0 3 0 5 7 9 1 0 8 0 0 0 6 0 1 0 0 0 0 6 0 9 0 0 0 0 1 0 0 0 0 0 0 0 0 6

输出样例#2：

说明

【数据范围】

40%的数据，数独中非

80%的数据，数独中非

100%的数据，数独中非

NOIP 2009 提高组第四题

题解：迭代搜素

如果剩下的格子我全部填九得到的分都没有当前的分高，停止搜索

按照数独的思想，要先从格子剩的少的地方填

对于第一个剪枝我每次都重新搜了一遍，后来发现可以预先处理，每次减掉一个格子的贡献(自己太也SB了)

还可以用位运算更快

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int M = 3e5 + 5, P = 3e5;int a[12][12], tot[12], z[12];int banx[12], bany[12], ban[12], bin[12];int id[12][12] = {{
     0},{
     0, 1, 1, 1, 2, 2, 2, 3, 3, 3},{
     0, 1, 1, 1, 2, 2, 2, 3, 3, 3},{
     0, 1, 1, 1, 2, 2, 2, 3, 3, 3},{
     0, 4, 4, 4, 5, 5, 5, 6, 6, 6},{
     0, 4, 4, 4, 5, 5, 5, 6, 6, 6},{
     0, 4, 4, 4, 5, 5, 5, 6, 6, 6},{
     0, 7, 7, 7, 8, 8, 8, 9, 9, 9},{
     0, 7, 7, 7, 8, 8, 8, 9, 9, 9},{
     0, 7, 7, 7, 8, 8, 8, 9, 9, 9}};int sc[12][12] = {{
     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 ans = -1, res;void dfs(int dep, int sum, int y){    if(dep == 10){        ans = max(ans, sum); return ;    }    if(ans != -1 && sum + res <= ans) return ;    int x = z[dep], tmp = 0;    while(a[x][y])y++;    if(y == 10) dfs(dep+1, sum, 1);    else {        for(int i = 9; i; i--)            if(!(banx[x]&bin[i]) && !(bany[y]&bin[i]) && !(ban[id[x][y]]&bin[i])){                banx[x]^=bin[i];bany[y]^=bin[i];ban[id[x][y]]^=bin[i];                res -= 9 * sc[x][y], a[x][y] = i;                 int to = y + 1; while(a[x][to])to++;                if(to == 10)dfs(dep+1, sum + i*sc[x][y], 1);                else dfs(dep, sum + i*sc[x][y], to);                res += 9 * sc[x][y], a[x][y] = 0;                banx[x]^=bin[i];bany[y]^=bin[i];ban[id[x][y]]^=bin[i];            }        }    }bool cmp(int a, int b){
    return tot[a] > tot[b];}int main(){//    freopen("hehe.out","w",stdout);    int now = 0, fg = 0;    bin[1] = 1;    for(int i = 2; i <= 9; i++) bin[i] = bin[i-1]<<1;    for(int i = 1; i <= 9; i++)        for(int j = 1; j <= 9; j++){            scanf("%d", &a[i][j]);            if(a[i][j]){                if(banx[i]&bin[a[i][j]]) fg = 1;                if(bany[j]&bin[a[i][j]]) fg = 1;                if(ban[id[i][j]]&bin[a[i][j]]) fg = 1;                tot[i]++;                banx[i] |= bin[a[i][j]];                bany[j] |= bin[a[i][j]];                ban[id[i][j]] |= bin[a[i][j]];                now += a[i][j] * sc[i][j];            } else res += 9 * sc[i][j];        }    for(int i = 1; i <= 9; i++)z[i] = i;    sort(z + 1, z + 1 + 9, cmp);    if(fg)return !printf("-1\n");    int xx = 1, yy = 1;    while(tot[z[xx]] == 9)xx++;    while(a[z[xx]][yy])yy++;    dfs(xx, 0, yy);    if(ans == -1) printf("-1");    else printf("%d\n",ans + now);}

View Code

转载于:https://www.cnblogs.com/EdSheeran/p/9904787.html

你可能感兴趣的文章