题解：P3032 [USACO11NOV] Binary Sudoku G

· · 题解

一看这道题，很容易联想起曾经学过的八数码，明显是启发式迭代加深搜索（A*）算法。

我们可以设置一个状态，就是对于每个 3\times3 的格子，每一行，每一列都有一个状态位，暂时定为 S（不需要修改）和 U（需要修改），对应 1 和 0。一共是 9+9+9 个，这可以进行状态压缩。

于是，这题的解法便出来了，是状态压缩迭代加深搜索。

进行标记操作和查询，可以使用异或和与操作。

unsigned int mark(unsigned int oriStat,int x,int y)
{
    oriStat^=1<<((x/3)*3+(y/3)+18);
    oriStat^=1<<(x+9);
    oriStat^=1<<(y);
    return oriStat;
}
int hasU(unsigned int oriStat,int x,int y)
{
    int ans=0;
    ans=ans||(~oriStat&(1<<((x/3)*3+(y/3)+18)));
    ans=ans||(~oriStat&(1<<(x+9)));
    ans=ans||(~oriStat&(1<<(y)));
    return ans;
}

然后为了使 A* 发挥效力，估价函数采用统计 U 个数的方式。

int test(unsigned int oriStat)
{
    int i,j,ans=0;
    for(i=0;i<9;++i)
    {
        for(j=0;j<9;++j)
        {
            if(hasU(oriStat,i,j))
            {
                ans++;
            }
        }
    }
    return ans;
}

A* 代码主程序

std::unordered_map<int,std::pair<unsigned char,int>> dis;
int aStar(unsigned int oriStat,unsigned int aimStat)
{
    int i,j,toStat;
    q.push({0,oriStat});
    dis[oriStat]={0,0};
    std::pair<int,unsigned int> r;
    while(!q.empty())
    {
        r=q.top();
        q.pop();
        dis[r.second].first=1;
        if(r.second==aimStat)
        {
            return dis[r.second].second;
        }
        for(i=0;i<9;++i)
        {
            for(j=0;j<9;++j)
            {
                toStat=mark(r.second,i,j);
                if(!dis[toStat].first&&hasU(r.second,i,j))
                {
                    dis[toStat].second=min(dis[toStat].second,dis[r.second].second+1);
                    q.push({dis[toStat].second+test(toStat),toStat});
                }
            }
        }
    }
    return -1;
}

AC 代码：

#include<stdio.h>
#include<queue>
#include<utility>
#include<unordered_map>
std::priority_queue<std::pair<int,unsigned int>,std::vector<std::pair<int,unsigned int>>,std::greater<std::pair<int,unsigned int>>> q;
int min(int a,int b)
{
    return a>b?a:b;
}
unsigned int mark(unsigned int oriStat,int x,int y)
{
    oriStat^=1<<((x/3)*3+(y/3)+18);
    oriStat^=1<<(x+9);
    oriStat^=1<<(y);
    return oriStat;
}
int hasU(unsigned int oriStat,int x,int y)
{
    int ans=0;
    ans=ans||(~oriStat&(1<<((x/3)*3+(y/3)+18)));
    ans=ans||(~oriStat&(1<<(x+9)));
    ans=ans||(~oriStat&(1<<(y)));
    return ans;
}
int test(unsigned int oriStat)
{
    int i,j,ans=0;
    for(i=0;i<9;++i)
    {
        for(j=0;j<9;++j)
        {
            if(hasU(oriStat,i,j))
            {
                ans++;
            }
        }
    }
    return ans;
}
std::unordered_map<int,std::pair<unsigned char,int>> dis;
int aStar(unsigned int oriStat,unsigned int aimStat)
{
    int i,j,toStat;
    q.push({0,oriStat});
    dis[oriStat]={0,0};
    std::pair<int,unsigned int> r;
    while(!q.empty())
    {
        r=q.top();
        q.pop();
        dis[r.second].first=1;
        if(r.second==aimStat)
        {
            return dis[r.second].second;
        }
        for(i=0;i<9;++i)
        {
            for(j=0;j<9;++j)
            {
                toStat=mark(r.second,i,j);
                if(!dis[toStat].first&&hasU(r.second,i,j))
                {
                    dis[toStat].second=min(dis[toStat].second,dis[r.second].second+1);
                    q.push({dis[toStat].second+test(toStat),toStat});
                }
            }
        }
    }
    return -1;
}
int main()
{
    int i,j,r,stat=(1<<27)-1;
    for(i=0;i<9;++i)
    {
        for(j=0;j<9;++j)
        {
            scanf("%1d",&r);
            if(r)
            {
                stat=mark(stat,i,j);
            }
        }
    }
    printf("%d",aStar(stat,(1<<27)-1));
    return 0;
}