2965 The Pilots Brothers' refrigerator

問題概要

冷蔵庫には4x4個の取っ手がついており、全てが開の状態にならないと開かない。
一つの取っ手の状態を反転させる（開→閉およびその逆）と、その取っ手と同じ行および列にある取っ手全ての状態が反転する。

取っ手の初期状態が与えられるとき、最短の手順で冷蔵庫のドアを開ける手順を出力せよ。
それが複数ある場合はどれを出力してもかまわない。

解法

全探索する。ただし、愚直にやると間に合わないので、
状態を一つの整数として表わし、反転の操作をXOR一回でできるようにする。

ソースコード

char in[4][5];
int cng[16];

int main(){
	rep(i,4)rep(j,4)rep(k,4)
	cng[i*4+j]|=1<<k*4+j|1<<i*4+k;
	
	int cur=0,ans=20,ansi;
	rep(i,4){
		gets(in[i]);
		rep(j,4)if(in[i][j]=='+')cur^=1<<i*4+j;
	}
	rep(i,1<<16)
	{
		int tmp=cur,b=0;
		for(int j=i;j;j&=j-1)b++;
		rep(j,16)if(i&1<<j)tmp^=cng[j];
		if(tmp)continue;
		if(b<ans)ans=b,ansi=i;
	}
	
	printf("%d\n",ans);
	rep(i,16)if(ansi&1<<i)printf("%d %d\n",i/4+1,i%4+1);
	return 0;
}