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

麻烦哪位大牛也好 小牛也好 帮忙看一下我的BFS+位运算为什么超时 谢谢

Posted by ice_of_shadow at 2010-06-21 22:05:19 on Problem 2965
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=70000;
int a[6][6]={0};
int change[5][5]={{0},{0,0xf888,0xf444,0xf222,0xf111},{0,0x8f88,0x4f44,0x2f22,0x1f11},{0,0x88f8,0x44f4,0x22f2,0x11f1},{0,0x888f,0x444f,0x222f,0x111f}};
int que[700000];
int pre[N]={0},c[N],r[N],step[N];
int flag[N]={0};
int ans1[N],ans2[N];
int main()
{
	//freopen("data.in.txt","r",stdin);
	int i,j;
	int k=0;
	char d;
	for(i=1;i<=4;i++)
	{
		for(j=1;j<=4;j++)
		{
			scanf("%c",&d);
			if(d=='+')
				k+=1<<(16-(i-1)*4-j);
		}
		getchar();
	}
	int p=0,q=0,t,state;
	que[p++]=k;
	pre[k]=-1;
	while(q<=p)
	{
		t=que[q];
		if(t==0)
			break;
		if(flag[t]==0)
		{
			flag[t]=1;
			for(i=1;i<=4;i++){
				for(j=1;j<=4;j++)
				{
					state=t^change[i][j];
					if(!flag[state])
					{
						que[p++]=state;
						pre[state]=t;
						r[state]=i;
						c[state]=j;
						step[state]=step[t]+1;
						if(state==0)
							break;
					}
				}
				if(state==0)
					break;
			}
			if(state==0)
				break;
		}
		q++;
	}
	cout<<step[0]<<endl;
	t=0;
	for(i=1;i<=step[0];i++)
	{
		ans1[i]=r[t];
		ans2[i]=c[t];
		t=pre[t];
	}
	for(i=1;i<=step[0];i++)
		cout<<ans1[i]<<" "<<ans2[i]<<endl;	
	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