(POJ) 3279 Fliptile

传送门

题目大意：有一个m*n的格子，格子一面是白色的，一面是黑色的。现在需要将所有的格子都翻成白色的，但是由于牛蹄子很大，所以他每次翻一个都会影响到上下左右四个，现在让你求出最少的翻转次数，输出翻转矩阵。

解题思路：这个题虽然数据很小，但是如果我们简单的考虑每个格子的翻转情况，那会有2^mn种情况，直接pass，同一个格子当然是只能翻转一次，翻多次这是多余的。由于第一行的格子可以被下一行或者左右影响，那我们不如枚举第一行的所有翻转情况，那第二行的翻转情况就可以根据第一行来了，因为能修改第一行的只有第二行 了，如果第二行去修改第一行黑色格子，那任务是不可能完成的，这显而易见，这样我们一行一行的考虑下去，最后再判断一下最后一行是否全白就行了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 20
#define inf 0x3f3f3f3f
int n,m,a[maxn][maxn];
int temp[maxn][maxn],ans[maxn][maxn];
// 临时矩阵 结果矩阵
int dx[5]= {-1,0,0,0,1};
int dy[5]= {0,-1,0,1,0};
bool pd(int x,int y) {
	int s=a[x][y],i;//格子本身的状态在加上5个地方翻转的状态，%2就可知现在状态
	for(i=0; i<5; ++i) {
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=0 && nx<m && ny>=0 && ny<n)
			s+=temp[nx][ny];
	}
	if(s%2==0)	return 1;//白色状态
	else	return 0;//黑色状态
}
int solve() {
	int i,j;
	for(i=1; i<m; ++i) {//从第二行开始
		for(j=0; j<n; ++j) {
			if(!pd(i-1,j)) {
				temp[i][j]=1;
			}
		}
	}
	//判断最后一行是否全部白色；
	for(i=0; i<n; ++i) {
		if(!pd(m-1,i)) {
			return -1;
		}
	}
	int tnum=0;
	for(i=0; i<m; ++i) {
		for(j=0; j<n; ++j) {
			tnum+=temp[i][j];
		}
	}
	return tnum;
}
int main() {
	while(scanf("%d%d",&m,&n)!=EOF) {
		int i,j;
		for(i=0; i<m; ++i) {
			for(j=0; j<n; ++j) {
				scanf("%d",&a[i][j]);
			}
		}
		int res=inf;
		for(i=0; i<1<<n; ++i) { //二进制枚举第一行的操作
			memset(temp,0,sizeof(temp));
			for(j=0; j<n; ++j) {
				temp[0][n-j-1]=i>>j&1; //将操作逐一取出放进数组
			}
			int num=solve();

			if(num>=0&&res>num) {
				res=num;
				memcpy(ans,temp,sizeof(temp));

			}
		}
		if(res==inf)	printf("IMPOSSIBLE\n");
		else {
			for(i=0; i<m; ++i) {
				for(j=0; j<n; ++j) {
					if(j<n-1)	printf("%d ",ans[i][j]);
					else	printf("%d\n",ans[i][j]);
				}
			}
		}
	}
	return 0;
}