HDU 1495 非常可乐 BFS

时间:2022-10-09 17:06:43

题目大意:中文题不说了。

题目思路:我有同学用GCD数论写出来的代码很简洁,但是很抱歉,数论蒟蒻,我觉得比赛的时候我没办法推出。如果用BFS的话思路很简单的,就是6方向广搜,只不过稍微麻烦点。具体看代码吧。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<iostream>
#define MAX 115
using namespace std; int vis[MAX][MAX][MAX],a,b,c,k; bool check(int s,int n,int m)
{
if(!vis[s][n][m] && s<=c && n<=a && m<=b && s>= && n>= && m>=)
return true;
return false;
} struct node
{
int s,n,m,step;
}; int BFS()
{
node now,next;
now.s=c;
now.n=;
now.m=;
now.step=;
queue<node>Q;
Q.push(now);
vis[c][][]=;
while(!Q.empty())
{
now=Q.front();
Q.pop();
if(now.s==k && now.m==k)
{
return now.step;
}
for(int i=;i<;i++)
{
if(i==)//s->n
{
if(now.s==)
continue;
if(now.s >= (a-now.n))
{
next.s=now.s-(a-now.n);
next.n=a;
} else
{
next.s=;
next.n=now.n+now.s;
}
next.m=now.m;
} else if(i==)//n->m
{
if(now.n==)
continue;
if(now.n >= (b-now.m))
{
next.n=now.n-(b-now.m);
next.m=b;
} else
{
next.n=;
next.m=now.m+now.n;
}
next.s=now.s;
} else if(i==)//m->n
{
if(now.m==)
continue;
if(now.m >= (a-now.n))
{
next.m=now.m-(a-now.n);
next.n=a;
} else
{
next.m=;
next.n=now.n+now.m;
}
next.s=now.s;
} else if(i==)//s->m
{
if(now.s==)
continue;
if(now.s >= (b-now.m))
{
next.s=now.s-(b-now.m);
next.m=b;
} else
{
next.s=;
next.m=now.m+now.s;
}
next.n=now.n;
} else if(i==)//n->s
{
if(now.n==)
continue;
if(now.n >= (c-now.s))
{
next.n=now.n-(c-now.s);
next.s=c;
} else
{
next.n=;
next.s=now.s+now.n;
}
next.m=now.m;
} else if(i==)//m->s
{
if(now.m==)
continue;
if(now.m >= (c-now.s))
{
next.m=now.m-(c-now.s);
next.s=c;
} else
{
next.m=;
next.s=now.s+now.m;
}
next.n=now.n;
} if(check(next.s,next.n,next.m))
{
vis[next.s][next.n][next.m]=;
next.step=now.step+;
Q.push(next);
}
}
}
return -;
} int main()
{
while(scanf("%d%d%d",&c,&a,&b),a+b+c)
{
if(a > b)
swap(a,b);
if(c%!=)
{
printf("NO\n");
continue;
} else
{
k=c/;
memset(vis,,sizeof(vis));
int ans=BFS();
if(ans==-)
printf("NO\n");
else
printf("%d\n",ans);
}
}
return ;
}