BFS题
一共有六种状态转移 一一枚举就好 设置一个标记数组。 用二重循环可以很清晰的解决代码长的问题
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int v[];
int sign[][][];
struct cup//记录遍历中3个水杯容藏可乐情况
{
int v[];
int step;
}temp; void pour(int a,int b)//倒水函数，把a杯子中的可乐倒到b杯子中
{
int sum=temp.v[a]+temp.v[b];
if(sum>=v[b])
temp.v[b]=v[b];
else
temp.v[b]=sum;
temp.v[a]=sum-temp.v[b];
} void bfs()
{
int i,j;
queue<cup>q;
cup cnt;
cnt.v[]=v[];
cnt.v[]=;
cnt.v[]=;
cnt.step=;
q.push(cnt);
memset(sign,,sizeof(sign));
sign[v[]][][]=;
while(!q.empty())
{
cnt=q.front();
q.pop();
if(cnt.v[]==cnt.v[]&&cnt.v[]==)
{
printf("%d\n",cnt.step);
return ;
} for(i=;i<;++i)
{
for(j=;j<;++j)
{
if(i!=j)//自己不倒水给自己
{
temp=cnt;//每个水位情况都要把所有操作枚举一遍，所以都要赋值为原始水位情况
pour(i,j);
if(!sign[temp.v[]][temp.v[]][temp.v[]])
{
temp.step++;
q.push(temp);
sign[temp.v[]][temp.v[]][temp.v[]]=;
}
}
}
}
}
printf("NO\n");
} int main()
{
while(scanf("%d%d%d",&v[],&v[],&v[])&&v[]||v[]||v[])
{
if(v[]>v[])
{
int t=v[];
v[]=v[];
v[]=t;
}
bfs();
}
return ;
}