题解 P1391 【方阵安排】

· · 题解

看到这道题，我们可以先想到简单粗暴的算法：枚举每个 0 的位置是否修改为 1，然后用 O(n^2) 的时间暴力检查方阵是否完美。加上适当的剪枝后，这个算法应该能通过 N \le 6 的部分。但是遇到 N \le 18 的部分就超时了。

考虑如何进一步优化。我们发现，时间主要浪费在“枚举每个 0 的位置是否修改”这个过程。因为 0 的位置数量接近 N^2，总的枚举情况就有了 2^{N^2} 种，无法接受。但是，我们真的要遍历整个方阵中所有 0 的位置吗？

我们考虑换一种思维方式。我们能否枚举出所有的完美的方阵，然后检查输入的初始方阵能否变换到这个方阵，并花费尽可能少的步数？

如果还是一个一个位置去枚举整个方阵，这样还是会超时。但是，如果我们能枚举出方阵的一部分，通过这一部分来确定整个方阵， 我们就可以极大地节省我们花费的时间。

我们考虑方阵中的一个格子 (x,y)，它的四周的四个格子是 (x+1,y),(x-1,y),(x,y+1),(x,y-1)。当这四个格子中的三个确定了，为了满足四周 1 的数量为偶数，最后一个格子是 0 还是 1 也能确定。那么就有了两种方案：

因为 N \le 18，一行或者一列只有 2^N 中情况。推出整个方阵并计算答案只需要 O(N^2) 的时间，总的时间复杂度为 O(2^N \times N^2)。

通过确定第一行推出整个矩阵的代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define rgt register int
#define qmn(a,b) a<b?a:b
using namespace std;

int n,ans=1010;  //18*18=324<1010，所以答案不可能达到 1010，如果枚举后 ans 值没有改变就是无解
int mtx[20][20],inx[20][20];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,-1,1};

void dfs(int xi,int g){

    if(xi>n){
        int tans=g;  //记录第一行变换的位置数
        for(rgt i=1;i<n;i++){
            for(rgt c,j=1;j<=n;j++){
                c=0;
                for(rgt tx,ty,k=1;k<4;k++){
                    tx=i+fx[k];
                    ty=j+fy[k];
                    if(tx>=1&&ty>=1&&tx<=n&&ty<=n){
                        if(mtx[tx][ty])
                            c++;
                    }
                }  //统计周围三个位置上 1 的数量
                if(c%2){  //确定下一行的对应位置上是 1
                    mtx[i+1][j]=1;
                    if(!inx[i+1][j])  //与初始矩阵不同
                        tans++;  //变换位置数+1
                }
                else{  //确定下一行对应位置上是 0
                    mtx[i+1][j]=0;
                    if(inx[i+1][j])  //因为 1 不能变换为 0，此方案不可行
                        return;
                }
            }
        }
        ans=qmn(ans,tans);  //取最小变换次数作为答案
        return;
    }

    mtx[1][xi]=inx[1][xi];  //得到初始矩阵的第一行
    dfs(xi+1,g);  //不变换
    if(!mtx[1][xi]){  //变换
        mtx[1][xi]=1;
        dfs(xi+1,g+1);
        mtx[1][xi]=0;
    }
}

int main(){
    scanf("%d",&n);
    for(rgt i=1;i<=n;i++)
        for(rgt j=1;j<=n;j++)
            scanf("%d",&inx[i][j]);

    dfs(1,0);
    if(ans==1010)
        printf("-1");
    else
        printf("%d",ans);

    return 0;
}