CCF NOIp 2009:靶形数独题解

主要思路

其实就是一道傻逼搜索题，按照位运算的方式来进行加速。读者可以考虑先看 位运算加速 Sudoku 这篇文章，了解如何使用位运算来搞定普通数独。

其实这道题在搞定了位运算数独之后就是一道暴力搜索题，只不过要记录答案还有可能性。其实笔者一开始是觉得这道题可能是 DP 或者是贪心法，没想到暴搜竟然就这样 AC 了。

见下文代码。

代码

// CH2901.cpp
#include <iostream>
#include <cstdio>
#define lowbit(num) (num & -num)
using namespace std;
const int VAL[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}};

int map[81], X[81], Y[81], BOX[81], counter[(1 << 9)], slist[(1 << 9)];
int answer[81];
int sx[9], sy[9], sb[9], tmp, ans = 0;
void setStat(int pos, int k) { tmp = 1 << k, sx[X[pos]] ^= tmp, sy[Y[pos]] ^= tmp, sb[BOX[pos]] ^= tmp; }
int getCnt(int num)
{
    int cnt = 0;
    while (num > 0)
        cnt++, num -= lowbit(num);
    return cnt;
}
int getFactor(int pos)
{
    if (X[pos] == 0 || X[pos] == 8 || Y[pos] == 0 || Y[pos] == 8)
        return 6;
    if (X[pos] == 1 || X[pos] == 7 || Y[pos] == 1 || Y[pos] == 7)
        return 7;
    if (X[pos] == 2 || X[pos] == 6 || Y[pos] == 2 || Y[pos] == 6)
        return 8;
    if (X[pos] == 3 || X[pos] == 5 || Y[pos] == 3 || Y[pos] == 5)
        return 9;
    return 10;
}
void dfs(int remain, int prev)
{
    if (!remain)
    {
        if (ans < prev)
        {
            ans = prev;
            for (int i = 0; i < 81; i++)
                answer[i] = map[i];
        }
        return;
    }
    int min_val = 2e9, id;
    for (int i = 0; i < 81; i++)
        if (map[i] == 0)
        {
            int stat = sx[X[i]] & sy[Y[i]] & sb[BOX[i]];
            if (stat == 0)
                return;
            if (counter[stat] < min_val)
                min_val = counter[stat], id = i;
        }
    int stat = sx[X[id]] & sy[Y[id]] & sb[BOX[id]];
    while (stat > 0)
    {
        int digit = slist[lowbit(stat)];
        setStat(id, digit);
        map[id] = digit + 1;
        dfs(remain - 1, prev + VAL[X[id]][Y[id]] * (digit + 1));
        setStat(id, digit);
        map[id] = 0;
        stat -= lowbit(stat);
    }
}
int main()
{
    for (int i = 0; i < 81; i++)
        scanf("%d", &map[i]);
    for (int i = 0; i < 81; i++)
        X[i] = i / 9, Y[i] = i % 9, BOX[i] = (int)(X[i] / 3) * 3 + (int)(Y[i] / 3);
    for (int i = 0; i < 9; i++)
        slist[1 << i] = i;
    for (int i = 0; i < (1 << 9); i++)
        counter[i] = getCnt(i);
    for (int i = 0; i < 81; i++)
        sx[i] = sy[i] = sb[i] = (1 << 9) - 1;
    int rm = 81;
    for (int i = 0; i < 81; i++)
        if (map[i] != 0)
            setStat(i, map[i] - 1), rm--;
    dfs(rm, 0);
    int sum = 0;
    for (int i = 0; i < 81; i++)
        sum += (answer[i]) * VAL[X[i]][Y[i]];
    if (ans == 0)
        printf("-1");
    else
        printf("%d", sum);
    return 0;
}