2019-06-05 poj3279

POJ 3279 Fliptile(反转+二进制枚举）

如果先假设第一行的操作数已经确定，接下来操作第二行，
假设现在第一行的第二个元素还不满足条件，那么只有通过
操作第二行第二个元素来改变，以此类推。因此一旦第一行操作
确定了，那么本次所有的操作便唯一确定，剩下的只需求出
操作数即可。因为对同一个地方操作两次跟没有操作是一样的。
操作三次跟一次是一样的，因此一个地方其实只有操作一次
或不操作两种选择，对第一行的每种情况进行枚举，一共
2^n中情况，每种情况可以在knm的时间内完成(k是常数，这里大约是5)
因此这个的复杂度5nm*2^n可以在规定时间内求出。
原文：https://blog.csdn.net/albertluf/article/details/79304639
样例：

代码实行：（二进制）
参考：

//二进制+BFS 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#define N 10010

using namespace std;
const int INF = 1e9+5;
const int maxn=20;
int n,m;
int a[maxn][maxn];
int  b[maxn][maxn];
int op[maxn][maxn];
int dir[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}}; //向哪个方向走 
bool judge(int x,int y){//判断 
    int ans=a[x][y];
    for(int i=0;i<5;i++){
        int xx=x+dir[i][0],yy=y+dir[i][1];
        if(xx<0||xx>=n||yy<0||yy>=m)continue;
        ans+=b[xx][yy]; 
    } 
    if(ans&1)return 0;
    return 1;
}
int flip(){

    int i,j;
    for(i=1;i<n;i++){
        for(int j=0;j<m;j++){
        if(!judge(i-1,j))//上一个不满足条件，则再次操作 
            b[i][j]=1;
        }
    }
        for(i=0;i<m;i++)
            if(!judge(n-1,i))
                return -1;
        int res=0;
        for(int i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                res += b[i][j];
        return res;
}
 int main()
 {
    int i,j;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int res=1e9;
    for(int i=0;i<1<<m;i++)
    {
        memset(b,0,sizeof(b));
        
        for(int j=0;j<m;j++)
            b[0][j] = i >> j & i;
            
        int num=flip();
        if(num!= -1 && num < res){
            res=num;
            memcpy(op,b,sizeof(b));
            }
    }
    if(res == 1e9)printf("IMPOSSIBLE\n");
    else {
        for(int i=0;i<n;i++){
            for(int j=0;j<m-1;j++)
                printf("%d ",op[i][j]);
            printf("%d\n",op[i][j]);
        }
    }       
        
     return 0;
 }

结果：