Mayflyyh
Mayflyyh
MayFlyyh's Blog
POJ 3279 Fliptile
> 给一个N行M列的矩阵,值分别为0和1,每次你可以选择将一个变成相反状态,同时,它周围的四个数也会变为相反状态。 
问:最少翻转多少次,可以将所有值都变成0 
多个解,输出翻转次数最少的(若有次数相同解,输出字典序小的) 
若无解,输出”IMPOSSIBLE”

显然一个数字只能翻转一次,那就按照字典序枚举第一行的所有可能,记录下答案最小的一个。然后每一个数看它上面是否为0,如果是就不管,如果不是就要反转当前的数字。
实现细节还是要注意的,感觉统计当前状态的思路也不错。

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
int dx[5]={0,0,-1,0};
int dy[5]={1,-1,0,0};
int a[25][25];
int f[25][25];
int ans[25][25];
int best=inf;   int m,n;
inline int  Judge(int x,int y){
    int tmp=a[x][y];
    for(int i=0;i<=3;++i){
        int gx=x+dx[i];
        int gy=y+dy[i];
        if(gx<1||gy<1||gx>m||gy>n) continue;
        tmp+=f[gx][gy];
    }
    return tmp&1;
}
int main (){
//  freopen("data.txt","r",stdin);
//  freopen("my.out","w",stdout);   
    while(scanf("%d %d",&m,&n)!=EOF){
        best=inf;
    for(int i=1;i<=m;++i) 
        for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]);
    for(int i=0;i<=(1<<n)-1;++i){
        memset(f,0,sizeof(f));
        for(int j=1;j<=n;++j){
            f[1][n-j+1]=(i>>(j-1))&1;
        }
        for(int k=2;k<=m;++k){
            for(int j=1;j<=n;++j){
                if(Judge(k-1,j))
                    f[k][j]=1;
            }
        }
        int flag=1;
        for(int k=1;k<=n;++k){
            if(Judge(m,k)){
                flag=0;
                break;
            }
        }
        if(flag==1){
            int tmp=0;
            for(int k=1;k<=m;++k){
                for(int j=1;j<=n;++j){
                    tmp+=f[k][j];
                }
            }
            if(tmp<best){
                best=tmp;
                for(int k=1;k<=m;++k){
                    for(int j=1;j<=n;++j){
                        ans[k][j]=f[k][j];
                    }
                }
            }
        }
    }
    if(best==inf){
        printf("IMPOSSIBLE");
    }
    else{
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(j==n)
                    printf("%d\n",ans[i][j]);
                else
                    printf("%d ",ans[i][j]);
            }
        }
    }
}
    return 0;
}
```
本文链接:http://www.mayflyyh.com/archives/279
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      搜索      POJ 3279 Fliptile
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

POJ 3279 Fliptile
> 给一个N行M列的矩阵,值分别为0和1,每次你可以选择将一个变成相反状态,同时,它周围的四个数也会变为相反状态。 问:最少翻转多少次,可以将所有值都变成0 多个解,输出翻转次数…
扫描二维码继续阅读
2018-07-16