emm 为什么题解区大佬都不愿意用状压啊……

看到这题的数据范围：

• 对于 $100 \%$ 的数据，保证 $n \leq 18$。

而众所周知，int 类型的变量可以存储 32 位带符号整数（去除符号位共 31 位）。也就是说，在这题中，我们甚至不需要 long long 就能将题目中方阵的一行塞到一个变量里（状态压缩）。
思路和其他几篇题解大致相同，但是貌似细节上还是不太一样，并且我的码量介于题解区另外两位大佬之间。
思路简述：

1. 枚举第一行可能出现的所有状态（状态压缩）
2. 对于每一种状态：
   1. 验证其是否合法，若其不合法则直接进入下一种状态
   2. 若其合法，则使用一个循环，数出从原方阵的第一行转移到此状态所需要的步骤
   3. 对其进行深度优先搜索：
      1. 根据传入的状态推导出下一行（程序里有详细过程）
      2. 在下一行重复此过程

对于这个思路，我们需要考虑一个问题：什么样的状态是不合法的？
很显然，题目中有明确表述，女生可以改♂成男生，但是男生不能改♂成女生。（女拳震怒
还是结合程序说实际一些：

//Luogu-P1391 
//Luogu @Enterpr1se (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<cstdio>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;
int n,mp[20],temp,ans=0x7fffaded,sstep;
bool flag;
int bin_digit(int num,int id){//获取一个二进制数的第 id 位（最低位为第0位） 
    return ((num&(1<<id))>>id);
}
int min(int a,int b){
    return a<b?a:b;
}
void dfs(int id,int currln,int curstep,int prevln=0){
    if(id==n){//如果已经扫过整个方阵，并且没有出现不合法状态 
        ans=min(ans,curstep);//更新答案 
        return;
    }
    int surmal/*一个人周围已有的男生数*/,nextln=0/*下一行的状态*/,nstep=0/*到下一行为止总共的换人次数*/;
    for(regint i=1;i<=n;++i){
        surmal=bin_digit(currln,i-1)+bin_digit(currln,i+1)+bin_digit(prevln,i);//一个人周围的总男生数 = 左边 + 右边 + 上一行同一位置男生数 
        nextln+=((surmal&1)<<i);//更新状态（将新一位加入到下一行的状态中） 
        if((bin_digit(mp[id+1],i)^bin_digit(nextln,i))){//如果下一行该位置需要的人与原方阵中此位置的人性别不同 
            ++nstep;//增加一次换人 
            if(bin_digit(mp[id+1],i))/*若原方阵中此位置是男生*/ return;
        }
    }
    dfs(id+1,nextln,curstep+nstep,currln);//从下一行开始搜索 
    return;
}
signed main(){
    scanf("%d",&n);
    for(regint i=1;i<=n;++i)
        for(regint j=1;j<=n;++j,mp[i]<<=1)
            scanf("%d",&temp),mp[i]+=temp;//将新输入的一位加在末尾 
    for(regint i=0;i<(1<<(n+1));i+=2){//枚举第一行所有状态 
        sstep=0;//初始化 
        flag=true;
        for(regint j=1;j<=n;++j){//检查状态是否合法 并 算出第一行换人次数 
            if((bin_digit(mp[1],j)^bin_digit(i,j))){//类似于 Ln29 至 Ln32 
                ++sstep;
                if(bin_digit(mp[1],j)){
                    flag=false;
                    break;
                }
            }
        }
        if(flag) dfs(1,i,sstep);//如果状态合法 
    }
    printf("%d",((ans^0x7fffaded)?ans:-1));
    return 0;
}

注：这题的状压看着有些奇怪，因为我决定将二进制数的最低位留空（永远为 0），这样在获取二进制数某一位的时候更加方便。例如样例中第二行，在本程序中存储为 $ 1000_2 $。
$\mathtt{Thanks}\text{ }\mathtt{for}\text{ }\mathtt{reading.}\text{ }$