Fliptile （POJ - 3279， 思维 + 二进制枚举）

一.题目链接：

POJ-3279

二.题目大意：

给你一个图，只有 0 和 1.

0 表示白色，1 表示黑色.

每敲击一块砖，这块砖以及它周围四个方向的砖都会转变颜色.

问是否能够将砖块都变为白色

如果可以，输出在最小步数情况下，操作的最小字典序.

否则，输出 "IMPOSSIBLE"

三.分析：

二进制枚举对第一行的操作.

再又第 1 行的状态，确定第 2 行的操作 比如 (1, 2) 为 1，则必须敲击 (2, 2)

同理处理所有行.

之后，若最后一行全为 0，则说明此方案可行.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)15;
const int inf = 0x3f3f3f3f;

bool mp[M + 5][M + 5];///初始地图
bool ans[M + 5][M + 5];///最终操作方法
bool cur[M + 5][M + 5];///现已处理的地图
bool operation[M + 5][M + 5];///现操作方法

void press(int x, int y)
{
    cur[x][y] = !cur[x][y];
    cur[x + 1][y] = !cur[x + 1][y];
    cur[x - 1][y] = !cur[x - 1][y];
    cur[x][y + 1] = !cur[x][y + 1];
    cur[x][y - 1] = !cur[x][y - 1];
}

int solve(int m, int n)
{
    int step = 0;
    memcpy(cur, mp, sizeof(mp));
    for(int i  = 1; i <= n; ++i)
    {
        if(operation[1][i])
        {
            press(1, i);
            step++;
        }
    }
    for(int i = 2; i <= m; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(cur[i - 1][j])
            {
                operation[i][j] = 1;
                press(i, j);
                step++;
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(cur[m][i])
            return inf;
    }
    return step;
}

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    for(int i = 1;i <= m; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            scanf("%d", &mp[i][j]);
        }
    }
    int min_step = inf;
    for(int i = 0; i < (1<<n); ++i)
    {
        memset(operation, 0, sizeof(operation));
        for(int j = 0; j < n; ++j)
        {
            operation[1][n - j] = i>>j&1;///保证了字典序
        }
        int step = solve(m, n);
        if(step < min_step)
        {
            min_step = step;
            memcpy(ans, operation, sizeof(operation));
        }
    }
    if(min_step < inf)
    {
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1;j <= n; ++j)
            {
                printf("%d%c", ans[i][j], j == n ? '\n' : ' ');
            }
        }
    }
    else
        printf("IMPOSSIBLE\n");
    return 0;
}