POJ 1753 Flip Game（bfs+位压缩运算）

题意：一个4*4的棋盘，只有黑和白两种棋子，每次翻转一个棋子，并且其四周的棋子也跟着翻转，求棋盘全为黑或全为白时所需的最少翻转次数。

思路：暴力枚举。

一共16个棋子，所以可以用二进制来存储。后来看了一下别人的代码，发现居然可以用异或运算来计算翻转情况，方便了不少。

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

int t[20] = {                     //对应翻转情况
    51200, 58368, 29184, 12544,
    35968, 20032, 10016, 4880,
    2248, 1252, 626, 305,
    140, 78, 39, 19,
};

int ans=0;
bool vis[(1 << 16)];

struct node
{
    int ans;
    int step;
};

void bfs()
{
    memset(vis, false, sizeof(vis));
    queue<node>q;
    node p;
    p.ans = ans;
    p.step = 0;
    q.push(p);
    vis[ans] = true;
    while (!q.empty())
    {
        p = q.front();
        q.pop();
        if (p.ans == 0 || p.ans == 65535)
        {
            cout << p.step << endl;
            return;
        }
        for (int i = 0; i<16; i++)
        {
            node p1;
            p1.step = p.step + 1;
            p1.ans = p.ans^t[i];
            if (vis[p1.ans])   continue;
            vis[p1.ans] = true;
            q.push(p1);
        }
    }
    cout << "Impossible" << endl;
}

int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    int cnt = 15;
    for (int i = 0; i<4; i++)
    {
        char ch[10];
        cin >> ch;
        for (int j = 0; j<4; j++)
        {
            if (ch[j] == 'w')
            {
                ans += (1 << cnt);  //转化为十进制
            }
            cnt--;
        }
    }
    bfs();
    return 0;
}

POJ 1753 Flip Game（bfs+位压缩运算）

相关推荐