首页 > 代码库 > 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+奇偶性减枝//状压搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。