翻转瓷砖Fliptile（开关反转）- POJ 3279

题目：

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".

Input

Line 1: Two space-separated integers: M and N

Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white

Output

Lines 1.. M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.

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

概译：输入M×N的表格共黑白两种颜色，其中1代表黑色，0代表白色。当奶牛击中一个格子时，它的上下左右和自己都会翻转成相反颜色。选择最小的翻转次数使得翻转后全是白色，输出每块砖的击打次数。若有多种情况，则选择假定输出为一个字符串时的最小字典序答案。

同样是开关反转的问题，比较经典，与POJ-3276的不同之处是这道题目从线变成了面增加了难度。

思路是位运算的枚举。

可以先枚举出第一行的所有情况，然后对于每一种情况进行以下做法：同一块砖翻过来翻回去是没有意义的，所有每块砖最多敲击一次就行了。我们只要从第二行开始逐个检查，检查第i行第j块时，如果第i-1行的第j块经过判断是黑色的，则翻转一次第i行第j块使其变成白色。这样一遍操作之后，最后再检查一遍最后一行是否都是白色，若有黑色，就没机会翻转了，则这种情况为无解。

另外，对于第一行的枚举，可以从0到（1<<n）-1枚举i，然后对此i（视为二进制）的各位数字（为0或1）进行分别提取放进翻转方案的第一行，就可以得到所有的第一行可能翻转方案。需要对位运算知识稍有了解。

关键在于黑色瓷砖的判断和翻转的记录，详见代码。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int dx[5] = {1, -1, 0, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};

int m, n, ans = -1;
int tile[16][16], flip[16][16], final[16][16];
//tile为初始黑白瓷砖，flip[i][j]=1时为翻转这块瓷砖，final是最终输出

int get(int x, int y) { //判断这块砖被翻转之后是黑是白

    int c = tile[x][y]; //本身的原始色

    for (int i = 0; i < 5; i++) {

        int tx = x + dx[i], ty = y + dy[i];
        //只有它周围的五个砖（包括自己）在翻转时才会影响到它的颜色变化
        if (tx >= 0 && tx < m && ty >= 0 && ty < n)
            c += flip[tx][ty];
    }

    return c % 2;
}
int cal() {

    for (int i = 1; i < m; i++) //第一行预设好了，所以从第二行开始
        for (int j = 0; j < n; j++) {

            if (get(i - 1, j) != 0) //如果上面那个是黑砖，需要翻转下面这块砖来导致上面翻成白色
                flip[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 += flip[i][j]; //共翻转了几次
    return res;
}
int main() {
    //输入
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> tile[i][j]; //1是黑色，0是白色

    for (int i = 0; i < 1 << n; i++) { //枚举第一行的所有状态

        memset(flip, 0, sizeof(flip)); //每换一种新情况都要重新写flip
        for (int j = 0; j < n; j++) {
            flip[0][n - 1 - j] = i >> j & 1; //先移位再与1
        }

        int num = cal();
        if (num >= 0 && (ans < 0 || num < ans) ) { //记录最优解
            ans = num;
            memcpy(final, flip, sizeof(flip));
        }

    }
    //输出
    if (ans == -1)
        cout << "IMPOSSIBLE" << endl;
    else
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                printf("%d%c", final[i][j], j == n - 1 ? '\n' : ' ');

    return 0;
}