南阳理工OJ 21 三个水杯 宽度优先遍历

/*
用队列来宽度搜索
初始状态先入队，一个有六种相互倒水的可能，
把这些没有出现过的状态全部入队，依次检查。
如果检查到结果状态，就输出
如果队列为空，就输出-1
*/
#include<iostream>
#include<map>
using namespace std;
map<int,int>mm;//用来标记是否用过
int queue[1000],base,top,result,ra,rb,rc,a,b,c,term;
bool f(int &x,int &y,int rx,int ry)//把x 的水倒进y里，当然需要知道x的容量和y的容量
{
	if(x==0||y==ry)return(false);//如果到不成就返回
	int ta=a,tb=b,tc=c;//把原来的水存起来
	if(x<ry-y)y+=x,x=0;
	else x-=ry-y,y=ry;
	term=10000*a+100*b+c;//得出新的方案
	a=ta;b=tb;c=tc;//还原原来的水
	if(mm.find(term)==mm.end())//如果新状态没有出现过
	{
		mm[term]=mm[queue[base]]+1;//就标记一下，并且记录是第几步到的这里
		if(term==result)return(true);//如果新状态是最后结果，就返回真
		queue[top++]=term;//新方案入队
		return(false);//返回
	}
	return(false);//如果新方案出现过，什么都不做
}
int main()
{
	int T,x,y,z;
	cin>>T;
	while(T--)
	{
		top=base=0;
		cin>>ra>>rb>>rc;cin>>x>>y>>z;//输入abc的容量和要求的结果
		result=x*10000+y*100+z;mm[ra*10000]=0;queue[top++]=ra*10000;//把结果转换成整数，并且入队
		while(top!=base)//进入队列，一个一个检查
		{
			a=queue[base]/10000;b=(queue[base]/100)%100;c=queue[base]%100;//先把abc还原
			if(f(a,b,ra,rb)||f(a,c,ra,rc)||f(b,a,rb,ra)||f(b,c,rb,rc)||f(c,a,rc,ra)||f(c,b,rc,rb))break;
			base++;
		}
		if(mm.find(result)!=mm.end())cout<<mm[result]<<endl;//如果找到结果就输出最小步数
		else cout<<"-1\n";//否则输出-1
		mm.clear();
	}
	return(0);
}