PKU 2965-The Pilots Brothers' refrigerator

問題概要

4x4のスイッチがある.全てのスイッチをOFFにしろ。ただしあるスイッチをクリックするとその列とその行のスイッチ全てが反転される。

解法

単純に全探索だと間に合わないので半分全列挙する。

実装(C++)

#include <iostream>
#include <algorithm>
using namespace std;
string s[4];
int MAP[4][4];
void put(int x,int y){
	MAP[x][y]=!MAP[x][y];
	for(int i=0;i<4;i++){
		MAP[x][i]=!MAP[x][i];
		MAP[i][y]=!MAP[i][y];
	}
}
bool is_exit(){
	for(int i=0;i<4;i++)for(int j=0;j<4;j++){
		if(MAP[i][j])return false;
	}
	return true;
}
void show(){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			cout<<MAP[i][j];
		}
		cout<<endl;
	}
}
int encode(){
	int res=0;
	for(int j=0;j<16;j++){
		if(MAP[j%4][j/4])res|=1<<j;
	}
	return res;
}
int mincost[1<<16];
int main() {
	fill(mincost,mincost+(1<<16),(1<<17)-1);
	for(int i=0;i<4;i++)cin>>s[i];
	for(int i=0;i<4;i++)for(int j=0;j<4;j++){
		MAP[i][j]=(s[i][j]=='+');
	}
	int ans=(1<<16)-1;
	for(int i=0;i<1<<8;i++){
		for(int j=0;j<8;j++){
			if((i>>j)&1){
				put(j/4,j%4);
			}
		}
		int e=encode();
		if(__builtin_popcount(mincost[e])>__builtin_popcount(i)){
			mincost[e]=i;
		}
		for(int j=0;j<8;j++){
			if((i>>j)&1){
				put(j/4,j%4);
			}
		}
	}
	for(int i=0;i<4;i++)for(int j=0;j<4;j++){
		MAP[i][j]=0;
	}
	for(int i=0;i<1<<8;i++){
		for(int j=0;j<8;j++){
			if((i>>j)&1){
				put(j/4+2,j%4);
			}
		}
		int e=(encode())&65535;
		if(__builtin_popcount(ans)>__builtin_popcount(mincost[e])+__builtin_popcount(i)){
			ans=(i<<8)+mincost[e];
		}
		for(int j=0;j<8;j++){
			if((i>>j)&1){
				put(j/4+2,j%4);
			}
		}
	}
	cout<<__builtin_popcount(ans)<<endl;
	for(int j=0;j<16;j++){
		if((ans>>j)&1){
			cout<<j/4+1<<" "<<j%4+1<<endl;
		}
	}
	return 0;
}