洛谷 P10456 The Pilots Brothers‘ refrigerator

$\text{[Problem Discription]}$

给定一个 $4\times 4$ 的网格，每个网格有 $0,1$ 两种状态。求最少可以通过多少次操作使得整个网格全部变成 $1$。

每次操作你需要选定一个格点 $(i,j)$，然后把第 $i$ 行和第 $j$ 列的所有元素都取反（即 $0$ 变 $1$，$1$ 变成 $0$）。

$\text{[Analysis]}$

首先我们可以发现，对同一个格点进行两次操作是没有意义的，因为那等于没操作。

所以每个格点至多被操作一次。

一共才 $16$ 个格点，把所有格点从 $1$ 到 $16$ 标号，我们完全可以用一个 $16$ 位的二进制数表示是否对每个格点进行操作。

具体地，我们用二进制数 $\text{status}$ 表示每个格点的操作与否。如果 $\text{status}$ 的第 $i$ 位为 $1$，那么代表我们对编号为 $i$ 的格点进行操作；否则不进行。

$\text{status}$ 可能的取值一共只有 $2^{16}$ 种，枚举 $\text{status}$ 即可。

得到 $\text{status}$ 后，剩下的事情就完全类似于模拟了。

所以，总的思想类似于生成-测试法。

总的时间复杂度 $O(N^2\times 2^N)$，其中 $N$ 为格点数量。

$\text{Code}$

bool a[6][6];
int ans;int count_one(int x){int ret=0;for(int i=1;i<=16;i++)if (x&(1<<(i-1))) ret++;return ret;
}void implement(int x){int row=(x-1)/4+1,col=(x%4?x%4:4);for(int j=1;j<=4;j++) a[row][j]^=1;for(int i=1;i<=4;i++) a[i][col]^=1;a[row][col]^=1;
}bool check(){for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if (!a[i][j]) return false;return true;
}int main(){for(int i=1;i<=4;i++)for(int j=1;j<=4;j++){char c;cin>>c;if (c=='+') a[i][j]=false;else a[i][j]=true;}ans=(1<<16)-1;for(int i=0;i<(1<<16);i++){for(int j=1;j<=16;j++)if (i&(1<<(j-1))) implement(j); if (check()){if (count_one(i)<count_one(ans)) ans=i;}for(int j=1;j<=16;j++)if (i&(1<<(j-1))) implement(j);//复原 }printf("%d",count_one(ans));for(int i=1;i<=16;i++)if (ans&(1<<(i-1))){int row=(i-1)/4+1,col=(i%4?i%4:4);printf("\n%d %d",row,col);}return 0;
}