POJ.3279 Fliptile (搜索+二进制枚举+开关问题)

POJ.3279 Fliptile (搜索+二进制枚举+开关问题)

题意分析

题意大概就是给出一个map,由01组成,每次可以选取按其中某一个位置,按此位置之后,此位置及其直接相连(上下左右)的位置(如果有)的0变成1,1变成0。现在求需要按多少次,才能使得整个map全部变成0。

此题解法与 UVA.11464 Even Parity 有异曲同工之妙。

首先可以看出,最多每个位置按一次,因为再按的话,相当于没按。如果我们枚举每一个位置是否按的话,2^(n*n)的复杂度爆炸。

接着思考,其实相对来说,下一行是否按,可以根据上一行的情况来决定。举个例子,如果上一行为1,那么下一行是一定要按的,按之后可以让上一行变成0.那么下下一行也是这个道理。

所以可以仅仅枚举第一行,就可以一次判断出来整个棋盘哪个位置按了,哪个没按。

说道这里可见这个题是有开关问题的性质。

至于如何枚举第一行,这里涉及到二进制枚举的方法,有兴趣的读者可以直接看UVA.11464 Even Parity或者从网上找相关资料,这里不再赘述。

需要注意的一点是,要判断最后一行是否全部为0,如果不是白色,说明这种方案不可行。要舍弃。

代码总览

#include <cstdio>
#include <algorithm>
#include <cstring>
#define nmax 20
#define inf 1000000
using namespace std;
int mp[nmax][nmax],flip[nmax][nmax],ans[nmax][nmax];
int spx[5] = {0,0,1,0,-1};
int spy[5] = {0,1,0,-1,0};
int m,n;
int ret = 0;
bool check(int x, int y)
{
if(x>=0 && x <m && y>=0 && y<n) return true;
else return false;
}
int handle(int x, int y)
{
int temp = mp[x][y];
for(int i = 0;i<5;++i){
int nx = x + spx[i];
int ny = y + spy[i];
if(check(nx,ny)){
temp+=flip[nx][ny];
}
}
return temp % 2; }
int Process()
{
for(int i = 1;i<m;++i){
for(int j = 0;j<n;++j){
if(handle(i-1,j)){
flip[i][j] = 1;
}
}
}
for(int i = 0;i<n;++i){
if(handle(m-1,i)) return inf;
}
int temp = 0;
for(int i = 0;i<m;++i){
for(int j = 0;j<n;++j){
temp+=flip[i][j];
}
}
return temp;
}
void update()
{
for(int i = 0;i<m;++i){
for(int j = 0;j<n;++j){
ans[i][j] = flip[i][j];
}
}
}
int main()
{
while(scanf("%d %d",&m,&n) != EOF){
memset(mp,0,sizeof(mp));
memset(ans,0,sizeof(ans));
for(int i = 0;i<m;++i){
for(int j = 0;j<n;++j)
scanf("%d",&mp[i][j]);
}
ret = inf;
int temp = 0;
for(int i = 0;i<(1<<n);++i){
memset(flip,0,sizeof(flip));
for(int j = 0;j<n;++j){
flip[0][j] = 1&(i>>j);
}
temp = Process();
if(temp < ret){
ret = temp;
update();
}
}
if(ret == inf) printf("IMPOSSIBLE\n");
else{
for(int i = 0;i<m;++i){
for(int j = 0;j<n;++j){
if(j == 0) printf("%d",ans[i][j]);
else printf(" %d",ans[i][j]);
}
printf("\n");
}
} }
return 0;
}
上一篇:[BZOJ 1647][USACO 2007 Open] Fliptile 翻格子游戏


下一篇:状态压缩+枚举 POJ 3279 Fliptile