poj-3279

poj 3279

首先，对同一个格子翻转两次就会恢复原状，所以多次翻转是多余的。此外，翻转的格子的集合相同的话，其次序是无关紧要的。
所以对一个格子来说，反转奇数次相对于没有反转， 偶数次相当于反转
对于最后一行来说，如果并非全为白色，则意味着不存在可行的操作方法。

解法：先穷举第一行的翻转方式，然后可以很容易判断这样是否存在解以及解的最小步数是多少，这样将第一行的所有翻转方式都尝试一次就能求出整个问题的最小步数。这个算法中最上面
一行的翻转方式共有2^N种

#include<iostream>
#include<cstring>
using namespace std;

#define maxn 16

int tile[maxn][maxn];       // 初始状态
int filp[maxn][maxn];       // 中间状态
int opt[maxn][maxn];        // 目标状态
int m, n;

// 四个方向
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};

int get(int x, int y) {         // 获取颜色
    int c = tile[x][y];
    for(int i = 0;i < 5;i++) {
        int x1 = x + dx[i], y1 = y + dy[i];
        if(0 <= x1 && x1 < m && 0 <= y1 && y1 < n)      //边界
            c += filp[x1][y1];
    }
    return c % 2;   //奇数次 返回1 相当于不变 偶数次返回0
}

int calc() {
    for(int i = 1;i < m;i++) {
        for(int j = 0;j < n;j++) {
            if(get(i - 1, j) != 0) {        // 上一行为黑
                filp[i][j] = 1;
            }
        }
    }

    for(int i = 0;i < n;i++)
        if(get(m - 1, i) != 0) return -1;           // 最后一行颜色，如果有黑色 无解

    //反转次数
    int res = 0;
    for(int i = 0;i < m;i++) {
        for(int j = 0;j < n;j++) {
            res += filp[i][j];
        }
    }
    return res;
}

void solve() {
    int res = -1;

    for(int i = 0;i < (1 << n); i++) {    //从第一行记录开始反转,共有2^n个可能性
        memset(filp, 0, sizeof(filp));          // 初始化
        for(int j = 0;j < n;j++) {       // 开始确定第一行 穷举第一行的所有可能性
            filp[0][n - j - 1] = i >> j & 1;
        }

        int num = calc();       //交换次数
        int cnt = 1;
        if(num >= 0 && (res < 0 || res > num)) {
            //cout << "cnt: " << cnt++ << "res: " << res <<endl;
            res = num;
            memcpy(opt, filp, sizeof(filp));
        }
    }

    if(res < 0) {// 无解
        printf("IMPOSSIBLE\n");
    }
    else {
        //cout << "res: " << res << endl;
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                //cout << opt[i][j] << j + 1 == n ? "\n" : " ";
                printf("%d%c", opt[i][j], j + 1 == n ? '\n' : ' ');

            }
        }
    }
}

int main()
{
    cin >> m >> n;
    for(int i = 0;i < m;i++) {
        for(int j = 0;j < n;j++) {
            cin >> tile[i][j];
        }
    }
    solve();
    return 0;
}