| ||||||||||
| 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 | |||||||||
我错了,忘记了0也是参考点T.T改完AC,300+ms...还算凑和...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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator