算法学习：从poj上的Fliptile到开关问题

是一个关于二进制枚举以及模拟递推的小问题😳

写在前面：本人蒟蒻，写此分享来督促自己复习，并与大家分享有关开关问题的一些技巧以及例题代码

Fliptile题目链接
参考题解
翻转问题的主要技巧以及规律

详细内容见代码及注释

代码（如有疏漏之处，敬请指出）😁

//先用状态压缩的方法枚举第一行的翻转情况，然后通过第一行的情况来递推出第二行的情况
//即：已知了第一行的情况了，需要通过第二行来修正第一行的情况
//（因为第一行已经被枚举固定了，所以除了第二行之外，其他行无法修改第一行）
//以此类推：其他所有行的情况都可以被递推出（即：是已经固定的了）
//注意：除了最后一行，因为没有最后一行没有下一行来帮最后一行修正
//(所以最后一行也是固定的，无法修正，最后应该检查一下最后一行是否符合题意即可)
//关键是：由下一行来处理上一行（而且是垂直的上一行，因为只有垂直的上一行是固定的）

# include<iostream>
# include<algorithm>
# include<cstring>

using namespace std;

const int N = 20;
const int INF = 0x3f3f3f3f;

int n, m;
int a[N][N];            //原始数组
int b[N][N];            //保存翻转次数的数组
int c[N][N];            //记录答案的数组
int dx[] = {0, 1, 0, -1, 0}, dy[] = {0, 0, -1, 0, 1};   //其实棋子并不受下方棋子的影响

bool out(int x, int y)
{
    if(x < 0 || x >= n|| y < 0 || y >= m)  return true;
    else  return false;
}

int get_color(int x, int y)
{
    int color = a[x][y];                                //初始颜色（这里是a）
    for(int i=0; i<5; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(out(nx, ny))  continue;
        color += b[nx][ny];                             //这里是b
    }
    return color & 1;                                   //本层翻转后的颜色（是固定的）
    //翻转后的颜色等于初始颜色+翻转影响产生的颜色（上，下，左，右，中五个方向）
}

int flip(int s)
{
    for(int i=1; i<=m; ++i)  b[0][i-1] = (s>>(m-i)) & 1;
    
    for(int i=1; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            if(get_color(i-1, j))   b[i][j] = 1;  
            //由上一行的状态来递推出下一行的状态，因为上一行的上，左，右状态已经全部已知
            //而正是由上方的状态来递推出其下方的状态
        }
    }
    
    for(int i=0; i<m; ++i)   if(get_color(n-1, i))   return INF;        //检查最后一层
    
    int times = 0;
    for(int i=0; i<n; ++i)   for(int j=0; j<m; ++j)  times += b[i][j];  //得出最小翻转次数
    return times;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin>>n>>m;
    
    for(int i=0; i<n; ++i)  for(int j=0; j<m; ++j)   cin>>a[i][j];
    
    int ans = INF;
    //枚举的是第一行所有可能的翻转动作（即：翻(1)或不翻(0)）
    for(int i=0; i < (1<<m); ++i)        //状态压缩，枚举第一行所有可能的情况 ，后面的只需递推了
    {
        memset(b, 0, sizeof b);         //记得初始化b
        int t = flip(i);
        if(t < ans)
        {
            ans = t;
            memcpy(c, b, sizeof b);     //复制状态
        }
    }
    
    if(ans == INF)  cout<<"IMPOSSIBLE"<<endl;
    else
    {
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                cout<<c[i][j]<<' ';
            }
            cout<<endl;
        }
    }
    
    return 0;
}