九度OJ 教程87 广度优先搜索之《非常可乐》
[cpp]
//九度OJ 教程87 广度优先搜索之《非常可乐》
//http://ac.jobdu.com/problem.php?cid=1040&pid=86
#include <stdio.h>
#define MAXS 110
#include <string.h>
#include<queue>
using namespace std;
typedef struct E{
int a,b,c,t;
}E;
int mark[MAXS][MAXS][MAXS];
queue < E > Q;
void AtoB(int &a,int sa,int &b,int sb)
{
int temp=sb-b;
if(temp>a){b+=a;a=0;}
else {a-=temp;b=sb;}
}
bool isok(E temp,int maxc)
{
maxc>>=1;
return(temp.a==maxc&&temp.b==maxc||temp.a==maxc&&temp.c==maxc||temp.b==maxc&&temp.c==maxc);
}
int main()
{
int maxa,maxb,maxc;
while(~scanf("%d %d %d",&maxc,&maxa,&maxb)&&maxc)
{
if(maxc&1){puts("NO");continue;}
memset(mark,1,MAXS*MAXS*MAXS*sizeof(int));
while(Q.empty()==false)Q.pop();
E now,temp;
int flag;
now.a=now.b=now.t=0;
now.c=maxc;flag=0;
mark[0][0][maxc]=0;
Q.push(now);
while(Q.empty()==false&&flag==0)
{
now=Q.front();
Q.pop();
now.t++;
temp=now;
AtoB(temp.c,maxc,temp.b,maxb);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
}
temp=now;
AtoB(temp.a,maxa,temp.b,maxb);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
}
temp=now;
AtoB(temp.a,maxa,temp.c,maxc);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
}
temp=now;
AtoB(temp.b,maxb,temp.a,maxa);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
}
temp=now;
AtoB(temp.b,maxb,temp.c,maxc);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
} www.zzzyk.com
temp=now;
AtoB(temp.c,maxc,temp.a,maxa);
if(mark[temp.a][temp.b][temp.c])
{
mark[temp.a][temp.b][temp.c]=0;
if(flag=isok(temp,maxc))break;
Q.push(temp);
}
}
if(flag)printf("%d\n",now.t);
else puts("NO");
}
return 0;
}
补充：软件开发 , C++ ,
