欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(POJ) 3279 Fliptile

程序员文章站 2022-05-08 23:52:19
...

传送门

题目大意:有一个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;
}

 

相关标签: POJ