POJ3279

做过很多遍的二进制搜索，每次写就是对着代码敲一遍，然后下次写又不会

链接：http://poj.org/problem?id=3279

题意：n*m的矩阵，全是0和1构成的，当选择翻一个点的时候，周围的点会受到影响，问选择翻n*m矩阵中的哪些点，可以将所有点均翻过来？

为什么要用搜索？因为n和m很小，最大是15

为什么要用二进制搜索？因为是枚举状态，而且是每行每列的状态

怎么样枚举最好？枚举第一行，然后依次遍历其他行，枚举第一行的复杂度是2的n次方，然后遍历全矩阵式n*m，整个复杂度相乘没有问题

怎么搜索呢？

用一个整数表示1行的状态，比如255=11111111（2），那么循环就是从0到255表示256种情况，255的第0位至第7位均是1，所以呢，表示全部需要翻，然后从第二行到第n-1行依次推理得需要或者不需要翻，再用最后一行来检验方案是不是可行

const int maxn=20;
const int inf=0x3f3f3f3f;

int n,m;
int mp[maxn][maxn];
int mem[maxn][maxn];
int ans[maxn][maxn];

int mx[]={0,0,1,-1};
int my[]={1,-1,0,0};

bool ok(int x,int y){
	if (x<0||y<0||x>=m||y>=n) return false;
	return true;
}

bool calc(int x,int y){
	int ret=mp[x][y]+mem[x][y];
	for(int i=0;i<4;i++){
		int tx=x+mx[i];
		int ty=y+my[i];
		if (ok(tx,ty)) ret+=mem[tx][ty];
	}
	return ret%2; 
}

void nxt(int x,int y,int &tx,int &ty){
	tx=x;
	ty=y+1;
	if (ty==n){
		++tx;
		ty=0;
	}
}

int dfs(int x,int y,int num){
	if (x==m) return num;
	bool tem=calc(x-1,y);
	if (tem){
		mem[x][y]=true;
		++num;
	}
	int tx,ty;
	nxt(x,y,tx,ty);
	return dfs(tx,ty,num);
}

int search(int in){
	memset(mem,false,sizeof(mem));
	int ret=0;
	for(int i=0;i<n;i++)
		if ((in>>i)&1){
			mem[0][i]=true;
			++ret;
		}
	ret+=dfs(1,0,0);
	for(int i=0;i<n;i++)
		if (calc(m-1,i)) return inf;
	return ret;
}

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d%d",&m,&n)!=EOF){
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++) 
				scanf("%d",&mp[i][j]);
		int tem=inf;
		for(int i=0;i<(1<<n);i++){
			int rec=search(i);
			if (tem>rec){
				tem=rec;
				memcpy(ans,mem,sizeof(mem));
			}
		}
		if (tem==inf){
			puts("IMPOSSIBLE");
			continue;
		}
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				printf("%d%c",ans[i][j],j==n-1?'\n':' ');
	}
	return 0;
}