Description
一个黑白网格,点一次会改变这个以及与其连通的其他方格的颜色,求最少点击次数使得所有全部变成黑色.
Sol
高斯消元解异或方程组.
先建立一个方程组.
\(x_i\) 表示这个点是否被用过.
因为第二次使用同一个点,这个点的贡献就被消除了,所以每个点只会被用 0/1 次.
\(a_{ij}\) 表示 \(j\) 点对 \(i\) 是否有影响,有影响为 1 否则为 0.
最后的一位表示最后的状态^最初的状态.
这样就列出来了 \(n*m\) 个方程组,一共 \(n*m\) 个未知数.
然后求解,就跟高斯消元一样,用异或的方式消掉就可以了.
Code
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; #define H(i,j) ((i-1)*m+j)
const int N = 35; int n,m;
int a[N][N]; void print(){
cout<<"----------------------------"<<endl;
for(int i=1;i<=30;i++){
for(int j=1;j<=31;j++) cout<<a[i][j];
cout<<endl;
}
} void init(){
n=5,m=6;
for(int i=1;i<=n;i++){
char s[N];memset(s,0,sizeof(s));
scanf("%s",s+1);
for(int j=1;j<=m;j++) a[H(i,j)][n*m+1]=1^(s[j]-'0');
// cout<<a[H(i,j)][n*m+1];
// cout<<endl<<s+1<<endl<<endl;
} for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
a[H(i,j)][H(i,j)]=1;
if(i+1<=n) a[H(i,j)][H(i+1,j)]=1;
if(i-1>=1) a[H(i,j)][H(i-1,j)]=1;
if(j+1<=m) a[H(i,j)][H(i,j+1)]=1;
if(j-1>=1) a[H(i,j)][H(i,j-1)]=1;
}
// print();
} void gauss(int n){
for(int i=1,r,j;i<n;i++){
for(r=j=i;j<n;j++) if(a[j][i]) { r=j;break; }
// cout<<i<<" "<<r<<endl;
if(r!=i) for(int k=i;k<=n;k++) swap(a[i][k],a[r][k]);
for(int k=i+1;k<n;k++) if(a[k][i]) {
for(j=i;j<=n;j++) a[k][j]^=a[i][j];
}
// print();
}
// print();
for(int i=n-1;i;i--){
for(int j=i+1;j<n;j++) a[i][n]^=a[j][n]*a[i][j];
} } void out(){
int ans=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[H(i,j)][n*m+1]) ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[H(i,j)][n*m+1]) cout<<i<<" "<<j<<endl;
} int main(){
// freopen("in.in","r",stdin);
// freopen("log.out","w",stdout);
init();
gauss(31);
out(); return 0;
}