| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:bfs~~用位运算压缩,附代码In Reply To:bfs~~用位运算压缩,附代码 Posted by:lzxzy at 2018-10-06 16:44:01 #include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#define X 0x7fffffff
#define min(x,y) (x<y?x:y)
char in[7];
bool check[100000];
int d[20]={0,0xc800,0xe400,0x7200,0x3100,0x8c00,0x4e00,0x2700,0x1300,0x08c8,0x04e4,0x0272,0x0131,0x008c,0x004e,0x0027,0x0013};
struct node{
int that;
int ans;
}qu[10000010];
void bfs(int s)
{
int minn=X;
int head=1,tail=1;
check[s]=1;
qu[head].that=s;
qu[head].ans=0;
while(head<=tail)
{
for(int i=1;i<=16;i++)
{
int t=qu[head].that;
int u=t^d[i];
if (check[u]!=1){
++tail;
check[u]=1;
qu[tail].that=u;
qu[tail].ans=qu[head].ans+1;
if (u==65535||u==0) minn=min(minn,qu[tail].ans);
}
}
head++;
}
if (minn!=X) printf("%d\n",minn);
else printf("Impossible\n");
}
int main()
{
int s=0;
for(int i=1;i<=4;i++)
{
scanf("%s",in+1);
for(int j=1;j<=4;j++)
if (in[j]=='b') s=s*2+1;
else s*=2;
}
bfs(s);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator