POJ 3220 位运算+搜索

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

转载自：http://blog.csdn.net/lyhypacm/article/details/5813634

DES:相邻的两盏灯状态可以互换，给出初始状态。询问是否能在三步之内到达。如果能的话。输出不属。超出3步就输出more。

貌似典型应用是位压缩。我觉得各种按位运算用的也很巧妙。判断两盏灯是不是状态一样的时候，和交换状态的时候。先广搜一遍，保存到达各种状态的最短路径，然后查询就可以了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int maxn=<<; int visi[maxn];
//两点相连，一共有32条边
int a[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},
{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,}}; void BFS(int p)
{
int i;
visi[p]=;
queue <int> mq;
mq.push(p);
while(!mq.empty())
{
int t=mq.front();
mq.pop();
if(visi[t]>=) continue;
for(i=;i<;i++) //看下可以改变哪两个点
{
int p1,p2;
//表示a[i]灯的状态
p1=t&(<<(a[i][]-));
p2=t&(<<(a[i][]-));
if(p1==p2 || p1&&p2) continue; //两个灯状态一样
p1=t^(<<(a[i][]-));
p2=p1^(<<(a[i][]-)); //两个灯交换状态
if(visi[p2]==-) //如果是其它的值，说明此时步骤不是最小的
{
mq.push(p2);
visi[p2]=visi[t]+;
}
}
}
} int main()
{
int tes;
int x,i,j;
x=(<<)-(<<); //就是最终状态作为起始状态
memset(visi,-,sizeof(visi));
BFS(x);
scanf("%d",&tes);
for(i=;i<=tes;i++)
{
int sum=; //表示状态
for(j=;j<;j++)
{
int tmp;
scanf("%d",&tmp);
if(tmp==)
sum+=<<j;
} printf("Case #%d: ",i);
if(visi[sum]==-) //表示三步之内没达到
puts("more");
else printf("%d\n",visi[sum]);
}
return ;
}