BFS+位运算改变状态,不明白为啥WA
#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;
}

• 我错了,忘记了0也是参考点T.T改完AC,300+ms...还算凑和... (1010) majia6 2008-09-07 13:14:17