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

我错了,忘记了0也是参考点T.T改完AC,300+ms...还算凑和...

Posted by majia6 at 2008-09-07 13:14:17 on Problem 3185
In Reply To:为啥土土BFS就WA了....谁能给点建议....thx Posted by:majia5 at 2008-09-07 11:15:54
#include <iostream>
#include <list>
#include <map>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
bool hash[1048576];
int c[21]={0,1};
struct state
{
	int water,t;
}tmp,p;
queue<state> q;
int main()
{
	int i,hash_tmp=0,t,res=0;
	for(i=2;i<=20;i++)c[i]=c[i-1]*2;
	for(i=1;i<=20;i++)scanf("%d",&t),hash_tmp=2*hash_tmp+t;
	memset(hash,false,sizeof(hash));
	hash[hash_tmp]=true;
	tmp.water=hash_tmp;tmp.t=0;
	if(tmp.water==0)cout<<0<<endl;
	else{
	q.push(tmp);
	while(!q.empty())
		{
			tmp=q.front();tmp.t++;
			for(i=1;i<=20;i++)
				{
					p=tmp;
					//if((p.water&c[i])==c[i])
						{
							p.water^=c[i];
							if(i-1>=1)p.water^=c[i-1];
							if(i+1<=20)p.water^=c[i+1];
							if(hash[p.water])continue;
							q.push(p);
							hash[p.water]=true;
							if(p.water==0)break;
						}
				}
			q.pop();
			if(p.water==0)break;
		}	
	printf("%d\n",p.t);
	}

	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