P1391 方阵安排 题解

· · 题解

一个显而易见的结论：

我们可以通过第一行的状态，推出所有其他行的状态。

设我们已经处理好了前 i-1 行的状态，则我们可以确定第 i-1 行第 j 个格子正上方、正左方、正右方的格子中有多少个 1。我们可以根据这个数值的奇偶性推出第 i 行第 j 个格子的状态。

因此，我们可以只要枚举第一行的状态，复杂度 O(2^n)，允许范围内。

具体实现：使用二进制数进行操作，设一个 geti 函数，读取整数 x 在二进制状态下的第 i 位。

AC 代码：

#include<bits/stdc++.h>
#define int long long
#define geti(x,i) ((x>>(i-1))&1)
using namespace std;
int n,a[20][20],ans=0x3f3f3f3f,cnt;
void dfs(int x,int last,int now)
{
    if(x>n)
    {
        ans=min(ans,cnt);
        return;
    }
    if(cnt>=ans)return;
    int New=0,old=cnt;
    for(int i=1;i<=n;i++)
        if(!geti(now,i)&&a[x][i])return;
    for(int i=1;i<=n;i++)
        if(geti(now,i)&&!a[x][i])cnt++;
    for(int i=1;i<=n;i++)
    {
        int tmp=0;
        if(i>1)tmp+=geti(now,i-1);
        tmp+=geti(last,i);
        if(i<n)tmp+=geti(now,i+1);
        if(tmp&1)New|=1<<(i-1);
    }
    dfs(x+1,now,New);
    cnt=old;
}
main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]);
    for(int i=0;i<(1<<n);i++)
    {
        dfs(1,0,i);
    }
    if(ans!=0x3f3f3f3f)printf("%lld",ans);
    else printf("-1");
    return 0;
}