bfs 六种状态
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>
#include<stdexcept>
#include<iomanip>
#include<iterator>
using namespace std;
int s,n,m;
struct ss
{
int ml[4];
int step;
};
int vis[110][110][110];
void bfs ()
{
memset(vis,0,sizeof(vis));
queue<ss> q;
ss qq ,qqq;
qq.ml[0] = s;
qq.ml[1] = 0;//初始是0 不是n
qq.ml[2] = 0;
vis[qq.ml[0]][qq.ml[1]][qq.ml[2]] = 1;
qq.step = 0;
q.push(qq);
while (!q.empty())
{
qq = q.front();
q.pop();
if ((qq.ml[0] == s/2 && qq.ml[1] == s/2) || (qq.ml[0] == s/2 && qq.ml[2] == s/2) || (qq.ml[1] == s/2 && qq.ml[2] == s/2) )
{
printf("%d\n",qq.step);
return ;
}
//a b ok
{
//a b倒不完
if (qq.ml[0] > n - qq.ml[1] )
{
qqq = qq;
qqq.ml[0] = qq.ml[0] - (n- qq.ml[1]);
qqq.ml[1] = n;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//a b倒完
qqq = qq;
qqq.ml[0] = 0;
qqq.ml[1] = qq.ml[1] + qq.ml[0] ;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
//a c ok
{
//a c倒不完
if (qq.ml[0] > m - qq.ml[2] )
{
qqq = qq;
qqq.ml[0] = qq.ml[0] - (m - qq.ml[2]);
qqq.ml[2] = m;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//a c倒完
qqq = qq;
qqq.ml[0] = 0;
qqq.ml[2] = qq.ml[2] + qq.ml[0] ;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
//b a ok
{
//b a 倒不完
if (qq.ml[1] > s - qq.ml[0] )
{
qqq = qq;
qqq.ml[0] = s;
qqq.ml[1] = qq.ml[1] - (s - qq.ml[0]);
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//b a倒完
qqq = qq;
qqq.ml[1] = 0;
qqq.ml[0] = qq.ml[1] + qq.ml[0] ;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
// b c ok
{
//b c 倒不完
if (qq.ml[1] > m - qq.ml[2] )
{
qqq = qq;
qqq.ml[1] = qq.ml[1] - (m - qq.ml[2] );
qqq.ml[2] = m;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//b c 倒完
qqq = qq;
qqq.ml[2]= qq.ml[2] + qq.ml[1];
qqq.ml[1] = 0;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
//c a ok
{
//c a 倒不完
if (qq.ml[2] > s - qq.ml[0] )
{
qqq = qq;
qqq.ml[0] = s;
qqq.ml[2] = qq.ml[2] - (s - qq.ml[0]);
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//c a 倒完
qqq = qq;
qqq.ml[2] = 0;
qqq.ml[0] = qq.ml[0] + qq.ml[2] ;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
//c b ok
{
//倒不完
if (qq.ml[2] > n - qq.ml[1] )
{
qqq = qq;
qqq.ml[1] = n;
qqq.ml[2] = qq.ml[2] - (n - qq.ml[1]);
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
else
{
//倒完
qqq = qq;
qqq.ml[2] = 0;
qqq.ml[1] = qq.ml[1] + qq.ml[2] ;
qqq.step = qq.step + 1;
if(!vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]])
{
vis[qqq.ml[0]][qqq.ml[1]][qqq.ml[2]] = 1;
q.push(qqq);
}
}
}
}
printf("NO\n");
return ;
}
int main()
{
while (scanf("%d %d %d",&s,&n,&m) != EOF )
{
if (n == 0 && s == 0 && m ==0)
return 0;
if (s % 2 != 0 )
{
printf("NO\n");
}
else
{
bfs ();
}
}
return 0;
}