POJ – 1753 -Flip Game (搜索+位运算)

2018年1月31日 2 条评论 39 次阅读 1 人点赞

题目链接:POJ - 1753

题目大意:

有一个4*4的方格,每个方格中放一粒棋子,这个棋子一面是白色,一面是黑色。游戏规则为每次任选16颗中的一颗,把选中的这颗

以及它四周的棋子一并反过来,当所有的棋子都是同一个颜色朝上时,游戏就完成了。现在给定一个初始状态,要求输出能够完成

游戏所需翻转的最小次数,如果初始状态已经达到要求输出0。如果不可能完成游戏,输出Impossible。

题目分析:

本身这个题有一个很简单的做法,就是直接暴力搜索枚举。

不过我在网上发现了一种有趣的做法,通过位运算来模拟翻棋子的过程。

棋盘一共有16个位置可以选择,假设棋盘为0000 0000 0000 0000,假设翻左上角第一个,就变成了1100 1000 0000 0000,也就是51200,

以后每当一共数与这个数异或,就代表了翻转左上角第一个棋子。

提前算出16种情况代表的数,进行BFS即可。

给出代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
string s[5];
const int maxn=0x3f3f3f;
int change[16] = {
    51200,58368,29184,12544,
    35968,20032,10016,4880,
    2248,1252,626,305,
    140,78,39,19
};
int mark=65535;//二进制全为1
int vis[maxn];
struct node
{
    int state;
    int step;
    node(int x=0,int y=0)
    {
        state=x;
        step=y;
    }
};
int bfs(int states)
{
    vis[states]=1;
    queue<node> q;
    q.push(node(states,0));
    while(!q.empty())
    {
        node temp=q.front();
        q.pop();
        if(temp.state==0||temp.state==mark)
            return temp.step;
        for(int i=0;i<16;i++)
        {
            int x=temp.state;
            x=x^change[i];
            if(vis[x])
                continue;
            if(x==0||x==mark)
                return temp.step+1;
            vis[x]=1;
            q.push(node(x,temp.step+1));
        }
    }
    return -1;
}
int main()
{
    for(int i=0;i<4;i++)
        cin>>s[i];
    int states=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            states<<=1;
            if(s[i][j]=='b')
                states+=1;
        }
    }
    int ans=bfs(states);
    if(ans==-1)
        cout<<"Impossible"<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(2)

  • xq

    kls吼啊

    2018年2月2日
    • DLKKILL

      @xq 你怎么看见的==

      2018年2月3日