N - 非常可乐
================================================================================================================================
不用想的太复杂，其实就是一道广搜题，
三个瓶子有六种操作
s瓶→n瓶 s瓶→m瓶
n瓶→m瓶 n瓶→s瓶
m瓶→n瓶 m瓶→s瓶
只是比迷宫题的 上下左右 4个操作多了2种操作
然后判定条件变成 两个瓶子里的液体相同&&另一个瓶子里为空
再按照一般广搜的套路来，定义好列表，head ，tail 开始进行广搜
tail[head] 的初始状态 即三个瓶子的初始状态
s瓶 满的 n瓶 空的 m瓶 空的 step = 0
================================================================================================================================
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int s,n,m;
struct Node{
int s,n,m;
int step;
void in(int a,int b,int c,int d)
{
s=a,n=b,m=c;step=d;
}
}tail[];
bool book[][];
bool flag;
int head,top;
void caozuo(int i,int& ts,int& tn,int& tm)
{
if(i==) // s瓶→n瓶
{
tn+=ts;ts=; //s瓶全部倒入 n瓶
//tn表示当前的液体 ， n表示最多可容纳多少
if(tn>n) ts = tn-n,tn=n; //如果n瓶溢出了，则溢出的返回给s瓶
}
//下面的操作原理跟上面一样
if(i==) // s瓶→m瓶
{
tm+=ts;ts=;
if(tm>m) ts = tm-m,tm=m;
}
if(i==) // n瓶→s瓶
{
ts+=tn;tn=;
if(ts>s) tn = ts-s,ts=s;
}
if(i==) // n瓶→m瓶
{
tm+=tn;tn=;
if(tm>m) tn = tm-m,tm=m;
}
if(i==) // m瓶→s瓶
{
ts+=tm;tm=;
if(ts>s) tm = ts-s,ts=s;
}
if(i==) // m瓶→n瓶
{
tn+=tm;tm=;
if(tn>n) tm = tn-n,tn=n;
}
}
int main()
{
while(~scanf("%d %d %d",&s,&n,&m)&&s+n+m)
{
flag=;memset(book,,sizeof(book)); //初始化
if(n == m) printf("1\n"); //如果n==m，只需一步就可以达到目的
else
{
head = ;top = ;
tail[].in(s,,,); //队列【1】初始化
book[][]=;
while(head<top)
{
for(int i = ;i<=;++i)
{
int ts = tail[head].s;
int tn = tail[head].n;
int tm = tail[head].m;
caozuo(i,ts,tn,tm); //执行六个步骤
if(book[tn][tm]==) continue;
if(book[tn][tm]==)
{
book[tn][tm]=;
tail[top].in(ts,tn,tm,tail[head].step+);
++top;
}
//printf("ts : %d tn: %d tm: %d %d\n",ts,tn,tm,tail[top-1].step);
//↑可以直观的看到每一步三个瓶子的状况
if(tn==tm&&ts==||tn==ts&&tm==||ts==tm&&tn==) {flag=;break;}
}
head++;
if((flag==)) break;
}
if(flag) printf("%d\n",tail[top-].step);
else printf("NO\n"); }
}
}