POJ3279 Fliptile 枚举+简单搜索

题意:一个矩阵,每个点1或0,然后每次翻一个点,它周围上下左右(包括自己)1-》0,0-》1,问最少翻几次可以矩阵全是0,忽略题目说的字典序

分析:枚举第一行所有的情况,然后下面几行也随之确定了,然后看哪种好就行,因为每行宽最多15 所有二进制枚举一下。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<string>
using namespace std;
typedef long long LL;
const int maxn=;
const int INF=0x3f3f3f3f;
int o[maxn][maxn];
int now[maxn][maxn];
int temp[maxn][maxn];
int res[maxn][maxn];
int n,m,ans;
int dx[]= {,,-,};
int dy[]= {-,,,};
void change(int x,int y)
{
now[x][y]=-now[x][y];
for(int i=; i<; ++i)
{
int p=x+dx[i];
int q=y+dy[i];
if(p<||p>n||q<||q>m)continue;
now[p][q]=-now[p][q];
}
}
bool check(int x,int y)
{
if(now[x-][y])return true;
return false;
}
void solve(int x)
{
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
now[i][j]=o[i][j];
int a[maxn],cnt=,c=,flag=;
memset(temp,,sizeof(temp));
memset(a,,sizeof(a));
while(x)
{
a[++cnt]=x%;
x>>=;
if(a[cnt])++c;
}
for(int i=; i<=m; ++i)
if(a[i])change(,i),temp[][i]++;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
if(check(i,j))++c,change(i,j),temp[i][j]++;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
if(now[i][j])flag=;
if(!flag&&c<ans)
{
ans=c;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
res[i][j]=temp[i][j];
} }
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
scanf("%d",&o[i][j]);
ans=INF;
int l=(<<m);
for(int i=; i<l; ++i)
solve(i);
if(ans==INF)
{
printf("IMPOSSIBLE\n");
continue;
}
else
{
for(int i=; i<=n; ++i)
{
for(int j=; j<m; ++j)
printf("%d ",res[i][j]);
printf("%d\n",res[i][m]);
}
}
}
return ;
}
上一篇:Google Analytics:为链接点击设定事件追踪的方法


下一篇:java中StringBuffer与String、StringBuilder的区别