Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:bfs~~用位运算压缩,附代码

Posted by y0h123 at 2018-12-17 20:14:01 on Problem 1753
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator