POJ -3279 Fliptile(二進制枚舉， 搜尋）

​​POJ 3279​​

題目大意：

有一個 M * N 的格子，每個格子可以翻轉正反面，它們有一面是黑色，另一面是白色。黑色翻轉之後變成白色，白色翻轉之後則變成黑色。遊戲要做的是把所有的格子翻轉為白色。不過因為牛蹄很大，是以每次翻轉一個格子，與它上下左右相鄰接的格子也會被翻轉。求用最小的步數完成時，每個格子的翻轉次數。最小步數的解有多個時，輸出字典序最小的一組；解不存在的話，則輸出IMPOSSIBLE

分析：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>
#include <ctime>
#include <cstdlib>
//#pragma comment (linker, "/STACK:256000000")
using namespace std;
#define db(x) cout<<x<<endl

typedef long long ll;
const int N = 15 + 10;
const int INF = 0x3f3f3f;

int n, m;
int ori[N][N], tem[N][N];
int oper[N][N], ans[N][N];
int step = 0, minstep = INF;

void press(int x, int y) //異或兩次同一個數，等于沒有異或。
{
    tem[x][y] ^= 1;
    tem[x+1][y] ^= 1;
    tem[x-1][y] ^= 1;
    tem[x][y+1] ^= 1;
    tem[x][y-1] ^= 1;
}

bool solve()    //按第一行操作周遊全圖
{
    memcpy(tem, ori, sizeof(ori));
    for (int i = 1; i <= n; i++){
        if(oper[1][i]){
            press(1, i);
            step++;
        }
    }

    for(int i = 2; i <= m; i++){
        for (int j = 1; j <= n; j++){
            if(tem[i-1][j]){
                oper[i][j] = 1;
                press(i, j);
                step++;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if(tem[m][i])
            return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            scanf("%d", &ori[i][j]);
        }
    }
    for (int i = 0; i < (1 << n); i++){    //枚舉第一行狀态，按字典序枚舉
        memset(oper, 0, sizeof(oper));
        step = 0;
        for (int j = 0; j < n; j++){
            oper[1][n - j] = (i >> j & 1);
        }
        if(solve() && step > 0 && step < minstep){    //判斷是否有解及更新最優解
            minstep = step;
            memcpy(ans, oper, sizeof(oper));
        }
    }
    if(minstep < INF){
        for (int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                printf("%d ", ans[i][j]);
            }
            printf("\n");
        }
    }else{
        printf("IMPOSSIBLE\n");
    }
    return 0;
}

// n = 5;
// int x[n][n];
// for (int i = 0; i < (1 << n); i++)
// {
//     for (int j = 0; j < n; j++)
//     {
//         x[1][n - j] = (i >> j & 1);
//     }
//     for (int k = 1; k <= n; k++)
//     {
//         cout << x[1][k] << " ";
//     }
//     cout << endl;
// }