跳至正文

NOIP2009 靶形数独 解题报告

  • OI路程
  苦难的题目,我做着题只有一个想法:深搜,,暴力搜索!但是就连样例都超时了,我就直接找题解去了。
  网上找到一个题解,用位运算做的,大概看了下就开始仿造着写,去掉了感觉无用的功能(其实很有用),结果超时了。。。超时代码如下,75分。
#include <stdio.h>
#define getindex(t) ({\
        int i;\
        switch(t){\
        case 1:\
                i = 0;\
                break;\
        case 2:\
                i = 1;\
                break;\
        case 4:\
                i = 2;\
                break;\
        case 8:\
                i = 3;\
                break;\
        case 16:\
                i = 4;\
                break;\
        case 32:\
                i = 5;\
                break;\
        case 64:\
                i = 6;\
                break;\
        case 128:\
                i = 7;\
                break;\
        case 256:\
                i = 8;\
                break;\
        }\
        i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9],             //记录横排出现的数字
    col[9],             //记录竖排出现的数字
    box[9],             //记录九各宫出现的数字
    use[9];             //记录横排
int ans = –1;
//初始化为-1而不是0 
int map[9][9];
int mul[9][9] = {{666666666},
                 {677777776},
                 {678888876},
                 {678999876},
                 {6789,109876},
                 {678999876},
                 {678888876},
                 {677777776},
                 {666666666}};

void cal(void)
{
        int i, j;
        int tmp = 0;
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        tmp += map[i][j] * mul[i][j];
                }
        }
        if(tmp > ans){
                ans = tmp;
        }
}

void srch(int i)
{
        int j, x, y;
        int pos, p;
        if(i == 9){
                cal();
                return ;
        }
        x = 511 ^ use[i];
        if(x == 0){
                srch(i + 1);
                return;
                //掉了return  
        }
        y = x & -x;
        use[i] |= y;
        j = getindex(y);
        pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
        while(pos > 0){
                p = pos & -pos;
                pos ^= p;
                map[i][j] = getindex(p) + 1;
                rol[i] |= p;
                col[j] |= p;
                box[getboxid(i, j)] |= p;
                srch(i);
                rol[i] ^= p;
                col[j] ^= p;
                box[getboxid(i, j)] ^= p;
        }
        use[i] ^= y;
}

int main(void)
{
        int i, j;
        int p;
        freopen(“abc.txt”“r”stdin);
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        scanf(%d, &map[i][j]);
                        if(map[i][j] > 0){
                                use[i] |= 1 << j;
                                p = 1 << (map[i][j] – 1);
                                if(((rol[i] & p)) || ((col[j] & p))
                                        || ((box[getboxid(i, j)] & p))){
                                        printf(“-1\n);
                                        return 0;
                                }
                                rol[i] |= p;
                                col[j] |= p;
                                box[getboxid(i, j)] |= p;
                        }
                }
        }
        srch(0);
        printf(%d\n, ans);
        return 0;
}

  后来找了好久才想起来是把这个重要的剪枝去掉了(就是我认为不重要的部分。)
  修改代码如下:
#include <stdio.h>
#define getindex(t) ({\
        int i;\
        switch(t){\
        case 1:\
                i = 0;\
                break;\
        case 2:\
                i = 1;\
                break;\
        case 4:\
                i = 2;\
                break;\
        case 8:\
                i = 3;\
                break;\
        case 16:\
                i = 4;\
                break;\
        case 32:\
                i = 5;\
                break;\
        case 64:\
                i = 6;\
                break;\
        case 128:\
                i = 7;\
                break;\
        case 256:\
                i = 8;\
                break;\
        }\
        i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9],             //记录横排出现的数字
    col[9],             //记录竖排出现的数字
    box[9],             //记录九各宫出现的数字
    use[9];             //记录横排
int count[9];           //每行值为0的个数
int hk[9];              //按照这里的顺序进行深搜!! 重要剪枝
int ans = –1;
//初始化为-1而不是0 
int map[9][9];
int mul[9][9] = {{666666666},
                 {677777776},
                 {678888876},
                 {678999876},
                 {6789,109876},
                 {678999876},
                 {678888876},
                 {677777776},
                 {666666666}};

void cal(void)
{
        int i, j;
        int tmp = 0;
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        tmp += map[i][j] * mul[i][j];
                }
        }
        if(tmp > ans){
                ans = tmp;
        }
}

void srch(int t)
{
        int i, j, x, y;
        int pos, p;
        if(t == 9){
        //这里是t不是i 
                cal();
                return ;
        }
        i = hk[t];
        x = 511 ^ use[i];
        if(x == 0){
                srch(t + 1);
                return;
                //掉了return  
        }
        y = x & -x;
        use[i] |= y;
        j = getindex(y);
        pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
        while(pos > 0){
                p = pos & -pos;
                pos ^= p;
                map[i][j] = getindex(p) + 1;
                rol[i] |= p;
                col[j] |= p;
                box[getboxid(i, j)] |= p;
                srch(t);
                rol[i] ^= p;
                col[j] ^= p;
                box[getboxid(i, j)] ^= p;
        }
        use[i] ^= y;
}

int main(void)
{
        int i, j;
        int p;

        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        scanf(%d, &map[i][j]);
                        if(map[i][j] > 0){
                                use[i] |= 1 << j;
                                p = 1 << (map[i][j] – 1);
                                if(((rol[i] & p)) || ((col[j] & p))
                                        || ((box[getboxid(i, j)] & p))){
                                        printf(“-1\n);
                                        return 0;
                                }
                                rol[i] |= p;
                                col[j] |= p;
                                box[getboxid(i, j)] |= p;
                        }else{
                                count[i]++;
                        }
                }
        }
        for(i = 0; i < 9; i++){
                hk[i] = i;
        }

        for(i = 1; i < 9; i++){
                p = hk[i];
                for(j = i – 1; j >= 0 && count[hk[j]] > count[p]; j–){
                        hk[j + 1] = hk[j];
                }
                hk[j + 1] = p;
        }
        srch(0);
        printf(%d\n, ans);
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。