Hekyのblog

洛谷P1074 靶形数独

url: https://www.luogu.com.cn/problem/P1074

tag:
NOIP2009 提高组,搜索,剪枝,位运算,NOIP提高组,2009

思路:

  1. 核心变量解析
  1. 关键函数解析
  1. 算法流程
  1. 位运算优化点

参考: https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路,爱了爱了。

代码:

#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
    return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
    for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
    for (int i = 0; i < (1 << 9); i ++)
    {
        int t = i;
        while (t)
        {
            t &= t -1;
            o[i] ++;
        }
    }
    for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
    if (cnt == 0)
    {
        ans = max(ans, sum);
    }
    int mi = 10, x, y;
    for (int i = 0;  i< 9; i++)
        for (int j = 0; j < 9; j ++)
        {
            if (!a[i][j])
            {
                int t = r[i] & c[j] & e[i / 3][j / 3];
                if (o[t] < mi)
                {
                    mi = o[t], x = i, y = j;
                }
            }
        }
    int t = r[x] & c[y] & e[x / 3][y / 3];
    while (t)
    {
        int l = (t & -t);
        t -= l;
        a[x][y] = p[l];
        r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
        dfs(cnt -1, sum + gs(x, y));
        a[x][y] = 0;
        r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
    }
}
int main()
{
    init();
    int cnt = 0, sum = 0;
    for (int i = 0; i < 9;  i++)
        for (int j = 0; j < 9; j ++)
        {
            cin >> a[i][j];
            if (a[i][j])
            {
                r[i] -= 1 << a[i][j] - 1;
                c[j] -= 1 << a[i][j] - 1;
                e[i / 3][j / 3] -= 1 << a[i][j] -1;
                sum += gs(i, j);
            }else cnt ++;
        }
    dfs(cnt, sum);
    cout << ans << endl;
    return 0;
}

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »