Fliptile(枚举&DFS)

发布于 2020-09-02  0 次阅读


题目大意:

Fliptile
给你一个n × m 的矩阵,矩阵由0和1组成,可以选择一个点翻转
翻转:将该点以及该点上下左右的点翻转(0变1,1变0)
求将矩阵翻转成全为0的最小步数,若没有则输出“IMPOSSIBLE”

思路:

很经典的题目了,可以从第二行开始推,用第二行的翻转将第一行全变成0,同理,第三行变第二行为全0…
到最后一行时,判断该行是否为0,全为0即为这种方法可以。

对于第一行的状态可以直接枚举,枚举第一行翻转的情况(采取二进制的枚举方式),对于每次枚举的答案取最小即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=20;
int ans;
int mp[N][N], s[N][N], tmp[N][N];
int dirx[]={0,1,0,-1,0};
int diry[]={0,0,1,0,-1};
int n, m;

bool check(int x, int y){   //求得(x,y)的颜色
    int temp=mp[x][y];
    for(int i=0; i<5; i++){
        int xx=x+dirx[i];
        int yy=y+diry[i];
        if(xx>=1 && xx<=n && yy>=1 && yy<=m)    temp+=tmp[xx][yy];
    }
    return temp&1;
}

int dfs(){
    for(int i=2; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(check(i-1,j))    //上一行为黑色的地方翻转
                tmp[i][j]=1;

    for(int i=1; i<=m; i++)     //最后一行如果有黑色的就返回,该情况无效
        if(check(n,i))
            return INF;
    int temp=0;
    for(int i=1; i<=n; i++)     //计算当前枚举的情况的翻转次数
        for(int j=1; j<=m; j++)
            temp+=tmp[i][j];
    return temp;
}

void solve(){
    ans=INF;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>mp[i][j];
    
    for(int i=0; i<(1<<m); i++){    //枚举第一行的所有翻转的状态
        memset(tmp, 0,sizeof(tmp));
        for(int j=1; j<=m; j++)
            tmp[1][m-j+1]=(i>>(j-1)) &1;    //求得当前第一行的状态
        int cnt=dfs();
        if(cnt<ans){    //该解目前最优
            ans=cnt;
            memcpy(s, tmp, sizeof(tmp));    //将枚举的二维数组复制到答案中保存
        }
    }
    if(ans==INF)    {cout<<"IMPOSSIBLE"<<endl;   return ;}
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            cout<<s[i][j]<<" ";
        cout<<endl;
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生