题目描述
给定一个NM的01矩阵，每次可以选定一个位置，将它和它相邻格子的数取反。问：怎样操作使得所有格子都变为0。当有多组解时，优先取操作次数最小的；当操作次数相同时，优先取字典序最小的。
输入
第一行两个整数N和M。
接下来是一个NM的01原矩阵。
1 ≤ N，M ≤ 20
输出
输出NM的答案矩阵，若是无解则输出“ $IMPOSSlBLE$ ”
样例输入
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
样例输出
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
题解
暴力
高斯消元暴枚自由元的复杂度不会证。。。就没有写。
事实上，可以发现，如果枚举第一行怎么选的话，第一行确定了，第一行和第二行共同影响第一行，因此第二行就确定了；第二行确定了，第一、二、三行共同影响第二行，因此第三行就确定了；……；第 $n-2$ 、$n-1$ 、$n$ 行共同影响第 $n-1$ 行，因此第 $n$ 行就确定了。
所以只需要枚举第一行的选择，可以推出 $2sim n$行的选择，然后判断第$n$ 行是否成立即可。
二进制压一行为一个数，枚举第一行的选择，然后维护第 $i$ 行选了什么（代码中的 $b[]$ ），以及选择了前 $i$ 行后第 $i$ 行的状态时什么（代码中的 $c[]$ ）。如果 $c[n]=0$ 则可行，此时统计所有 $b[]$ 中1的个数即为选择的次数。
最后输出答案即可。
注意特判无解的情况，以及 $IMPOSSlBLE$ 中倒数第4个字母的情况，以及输出格式的情况。
时间复杂度 $O(n·2^m)$
#include <cstdio>
int cnt[1050000] , a[21] , b[21] , c[21] , ans[21];
int main()
{
int n , m , p , i , j , t , x , mn = 1 << 30;
scanf("%d%d" , &n , &m) , p = (1 << m) - 1;
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= m ; j ++ )
scanf("%d" , &x) , a[i] = a[i] << 1 | x;
for(i = 1 ; i <= p ; i ++ ) cnt[i] = cnt[i - (i & -i)] + 1;
for(i = 0 ; i <= p ; i ++ )
{
b[1] = i , c[1] = (i ^ (i << 1) ^ (i >> 1) ^ a[1]) & p;
for(j = 2 ; j <= n ; j ++ )
b[j] = c[j - 1] , c[j] = (b[j - 1] ^ b[j] ^ (b[j] << 1) ^ (b[j] >> 1) ^ a[j]) & p;
if(!c[n])
{
t = 0;
for(j = 1 ; j <= n ; j ++ )
t += cnt[b[j]];
if(t < mn)
{
mn = t;
for(j = 1 ; j <= n ; j ++ )
ans[j] = b[j];
}
}
}
if(mn == 1 << 30) puts("IMPOSSlBLE");
else
for(i = 1 ; i <= n ; i ++ )
for(j = m - 1 ; ~j ; j -- )
printf("%d%c" , (bool)(ans[i] & (1 << j)) , j ? ' ' : '
');
return 0;
}