【POJ - 3279】Fliptile（经典翻转问题）

浅浅的花香味﹌ 2021-11-26 17:32 186阅读 0赞

## [\-->Fliptile][--_Fliptile] ##

直接中文翻译：  
**Descriptions:**

给你一个01矩阵，矩阵大小为M x N。***（1 <= M , N <= 15）***  
每次操作选择一个格子，使得该格子与上下左右四个格子的值翻转。  
至少多少次操作可以使得矩阵中所有的值变为0？  
请输出翻转方案，若没有方案，输出***"IMPOSSIBLE”*** 。  
若有多种方案符合题意，请首先输出翻转次数最少的方案；若方案个数仍不唯一，则输出字典序最小的方案。

**Input**

第一行输入两个数：M和N。***（1 <= M , N <= 15）***  
接下来M行，每行N个数，其值只为0或1。

**Output**

输出M行，每行N个数。  
每个数代表该位置翻转次数

**Sample Input**

> 4 4  
> 1 0 0 1  
> 0 1 1 0  
> 0 1 1 0  
> 1 0 0 1

**Sample Output**

> 0 0 0 0  
> 1 0 0 1  
> 1 0 0 1  
> 0 0 0 0

**题目链接：**

[https://vjudge.net/problem/POJ-3279][--_Fliptile]

先按字典顺序枚举第一行的全部可能，再去推第2行，第3行......把这些行全部推成0，最后看最后一行，如果最后一行都是0，则成功，记录翻转次数。否则失败

**AC代码：**

#include <iostream>
    #include <cstdio>
    #include <fstream>
    #include <algorithm>
    #include <cmath>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cstring>
    #include <map>
    #include <stack>
    #include <set>
    #include <sstream>
    #define mod 1000000007
    #define eps 1e-6
    #define ll long long
    #define INF 0x3f3f3f3f
    #define MEM(x,y) memset(x,y,sizeof(x))
    #define Maxn 20
    using namespace std;
    int result;
    int n,m;
    int mp[Maxn][Maxn];//原始地图
    int tmp[Maxn][Maxn];//当前操作的地图
    int ans[Maxn][Maxn];//最优解地图
    int dt[][2] = { { -1, 0 }, { 1, 0 }, { 0, 0 }, { 0, -1 }, { 0, 1 } };//5个方向
    int getcolor(int x,int y)//得到(x,y)的颜色
    {
        int cnt=mp[x][y];
        for(int i=0; i<5; i++)
        {
            int tx=dt[i][0]+x;
            int ty=dt[i][1]+y;
            if(tx>=0&&tx<n&&ty>=0&&ty<m)
                cnt+=tmp[tx][ty];
        }
        return cnt%2;
    }
    int solve()
    {
        int cnt=0;
        for(int i=1; i<n; i++)//从第二行开始检查是否需要翻转
            for(int j=0; j<m; j++)
                if(getcolor(i-1,j))
                    tmp[i][j]=1;
        for(int i=0; i<m; i++)//检查最后一行是否全为0
            if(getcolor(n-1,i))
                return INF;
        for(int i=0; i<n; i++)//统计翻转次数
            for(int j=0; j<m; j++)
                cnt+=tmp[i][j];
        return cnt;
    }
    int main()
    {
        result=INF;
        cin>>n>>m;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin>>mp[i][j];
        for(int i=0; i<1<<m; i++)//按照字典序枚举第一行所以翻转可能
        {
            MEM(tmp,0);//初始化地图
            for(int j=0; j<m; j++)
                tmp[0][j]= i>>(m-(j+1)) & 1;//第一行的状态
            int sum=solve();//翻转的次数
            if(sum<result)//更新地图
            {
                result=sum;
                memcpy(ans,tmp,sizeof tmp);//tmp数组复制到ans
            }
        }
        if(result==INF)
            cout<<"IMPOSSIBLE"<<endl;
        else//输出
        {
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<m; j++)
                    cout<<ans[i][j]<<" ";
                cout<<endl;
            }
        }
    }

转载于:https://www.cnblogs.com/sky-stars/p/11195560.html

[--_Fliptile]: https://vjudge.net/problem/POJ-3279