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