POJ 3279 Fliptile

关于翻转问题

例:给定一个01串，现有翻转规则：

翻转某一个位置时其后面2个位置也会跟着翻转，也就是每次翻转都会翻转3个连续的位置。要将01串全部翻转为0，求最小的翻转次数

形似这类题的问题叫做翻转问题，也可以叫开关问题

原文出处 https://blog.csdn.net/ac_hell/article/details/51077320

解决方案

①.若某一个位置被翻转了n次，则其实际上被翻转了n%2次，因为翻转2k次相当与没翻转，翻转2k+1次相当于翻转了1次，因为要求最小翻转次数，所以对于某一个位置要么只（主动）翻转一次，要么不（主动）翻转。

②.分析易知翻转的顺序并不影响最终结果。（理解不了可自己举个例子在纸上模拟下）

③.现在我们着眼于第1个位置，可知若要将第1个位置进行翻转只有翻转它自己，因为没有其他位置的翻转会引起它的翻转。由①可知若第1个位置为1则必须且进行翻转（并将其后2个进行连带翻转）且以后不再进行翻转，因为再进行翻转就一共翻转了2次相当于没翻转。然后着眼于第2个位置，由于第1个位置不再进行翻转，所以要想翻转第2个位置只有翻转它自己，因为没有其他位置的翻转会引起它的翻转…………………以此类推直至最后剩下的个数＜3个，因为每次都翻转3个，而剩下的少于3个了就不再进行考虑了，此时只需判断剩下的是否全为0的即可，若不全为0，则不存在全部翻转为0的方案

POJ 3279

Description

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

题意

1代表黑色格子，0代表白色格子，目标是把黑色全翻转为白色

但翻转任意一个格子，与他相邻的格子都会被翻转

求解最小翻转方案

Code

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

const int inf = 0x3f3f3f3f;

bool a[20][20];
///a[i][j]若为1表示坐标为(i, j)的格子是黑色的，0表示白色
bool b[20][20];
///b[i][j]若为1表示(在当前方案中)坐标为(i, j)的格子作出翻转，0表示不转
bool ans[20][20];

int dx[] = {-1, 1, 0, 0, 0};
int dy[] = {0, 0, 0, -1, 1};
int n, m;
int step_min = inf;

///a[i][j]与b[i][j]都不代表翻转后(i, j)格子的颜色，可以用以下color函数找
bool color(int x, int y)
{
    int flag = a[x][y];
    ///它现在的颜色受其上下左右中是否翻转的影响
    for(int i = 0; i < 5; ++i)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m)
            flag += b[xx][yy];
    }
    return flag & 1;
}

int slove()
{
    int sum = 0;
    for(int i = 2; i <= n; ++i)///从第二行起检测是否需要反转
        for(int j = 1; j <= m; ++j)
            if(color(i - 1, j))///如果它上面是黑色，那么这格需要反转
                b[i][j] = 1;

    ///检测最后一行是否全白
    for(int i = 1; i <= m; ++i)
        if(color(n, i))
            return inf;

    ///计算总翻转次数
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            sum += b[i][j];
    return sum;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)///涉及坐标问题，下标从1开始
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];

    ///（按照字典序）枚举第一行所有的翻转方案
    for(int num = 0; num < (1 << m); ++num)
    {
        memset(b, 0, sizeof(b));
        for(int i = 1; i <= m; ++i)
            b[1][i] = num >> (m - i) & 1;

        int tem = slove();
        if(tem < step_min)
        {
            step_min = tem;
            memcpy(ans, b, sizeof(b));
        }
    }
    if(step_min == inf)
        cout << "IMPOSSIBLE" << '\n';
    else
    {
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                printf("%d%c", ans[i][j], j == m ? '\n': ' ' );
    }
    return 0;
}

部分代码解释

///（按照字典序）枚举第一行所有的翻转方案
for(int num = 0; num < (1 << m); ++num)

这就相当于一个集合有m个元素，则有（2 ^ m）个子集。

对应着，第一行有m个元素，有（2 ^ m）种翻转方案

for(int i = 1; i <= m; ++i)
            b[1][i] = num >> (m - i) & 1;

这是按照字典序枚举了第一行的所有翻转方案，效果如下