首页 > 代码库 > poj1753 bfs+奇偶性减枝//状压搜索

poj1753 bfs+奇偶性减枝//状压搜索

http://poj.org/problem?id=1753

题意:有个4*4的棋盘,上面摆着黑棋和白旗,b代表黑棋,w代表白棋,现在有一种操作,如果你想要改变某一个棋子的颜色,那么它周围(前后左右)棋子的颜色都会被改变(白变成黑,黑变成白),问你将所有棋子变成白色或者黑色最少的步数。

思路:

1、如果用一个4*4的数组存储每一种状态,不但存储空间很大,而且在穷举状态时也不方便记录。因为每一颗棋子都只有两种状态,所以可以用二进制0和1表示每一个棋子的状态,则棋盘的状态就可以用一个16位的整数唯一标识。而翻转的操作也可以通过通过位操作来完成。显然当棋盘状态id为0(全白)或65535(全黑)时,游戏结束。

2、对于棋盘的每一个状态,都有十六种操作,首先要判断这十六种操作之后是否有完成的情况,如果没有,则再对这十六种操作的结果分别再进行上述操作,显然这里就要用到队列来存储了。而且在翻转的过程中有可能会回到之前的某种状态,而这种重复的状态是不应该再次入队的,所以维护 Visit[i]数组来判断 id==i 的状态之前是否已经出现过,如果不是才将其入队。如果游戏无法完成,状态必定会形成循环,由于重复状态不会再次入队,所以最后的队列一定会是空队列。

3、由于0^1=1,1^1=0,所以翻转的操作可以通过异或操作来完成,而翻转的位置可以通过移位来确定。

 

AC代码:

#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>#include<queue>using namespace std;int change[16] ={    51200,58368,29184,12544,    35968,20032,10016,4880,    2248,1252,626,305,    140,78,39,19};bool visit[65536];struct Node{    int state;    int step;};int bfs(int state){    memset(visit,false,sizeof(visit));    queue<Node>q;    Node now,next;    now.state=state;    now.step=0;    q.push(now);    visit[state]=true;    while(!q.empty())    {        now=q.front();        q.pop();        if(now.state==0 || now.state==0xffff)            return now.step;        for(int i=0; i<16; i++)        {            next.state = now.state^change[i];            next.step = now.step+1;            if(visit[next.state]) continue;            if(next.state==0 || next.state==0xffff)                return next.step;            visit[next.state]=true;            q.push(next);        }    }    return -1;}int main(){    char str[4][5];    int state,ans;    while(scanf("%s",str[0])!=EOF)    {        for(int i=1; i<4; i++)            scanf("%s",str[i]);        state=0;        for(int i=0; i<4; i++)            for(int j=0; j<4; j++)            {                state<<=1;                if(str[i][j]==b)                    state+=1;            }        ans=bfs(state);        if(ans==-1) puts("Impossible");        else printf("%d\n",ans);    }    return 0;}

 

poj1753 bfs+奇偶性减枝//状压搜索