/*
问题:要用N,M,S三个杯子均匀分出2杯可乐，S=N+M,00,M>0。如果能够平分，请输出倒出可乐的最少次数，如果不能输出"NO"
输入:3个整数,S 可乐的体积，N和M是两个杯子的容量，以"0 0 0"结束
输出:若可以平分，输出最少要倒的次数，否则输出NO
输入:
7 4 3
4 1 3
0 0 0
输出:
NO
3思路:用四元组(x,y,z,t)表示一个状态，x,y,z表示3个瓶子中的体积，t表示从初始状态到该平分状态需要倾倒的次数的状态之间的相互扩展。平分状态第一次被搜索出的次数即为所求。若t不是最少次数，则状态为无效状态，将其舍弃。
关键:
1 需要一个倾倒函数，来标记两个杯子之间的状态
2 平分的时候只要3个杯子中任意2个杯子各的总体积的一半就可以
3 3个杯子两两相互倾倒共有6次，而且需要注意方向，a倒向b与b倒向a是不同的
4 初始化将s,n,m之间的剪枝状态置为false,注意每次使用之前清空队列，每次设定起始节点，并设置剪枝状态
5 int puts(char* str)，将字符串写到标准输出上，成功返回非负值，失败返回EOF
6 注意更新后的状态必须要用更新后的东西,初始体积必须为偶数，否则不能平分。注意iVa -= (iConB - iVb)必须先求，放在后面值都改变了
*/#include
#include
#include
#include
#define N 50using namespace std;typedef struct Stat
{int x,y,z;//三个瓶子的体积int t;//从初始状态到平分状态的倾倒次数
}Stat;bool mark[N][N][N];//剪枝状态
int maze[N][N][N];//queue queueStat;//保存状态的队列//倾倒函数，iConA是容器A的体积,iVa是容器A中的原来的体积。将容器A中体积倒网容器B中，注意要用引用
void Dump(int iConA,int& iVa,int iConB,int& iVb)
{//注意，由于容器没有刻度，要么将一个容器中的所有可乐全倒，或者将另一个容器加满//如果B容器能够容纳A容器中所有可乐，则全部倒出if(iConB >= iVa + iVb){iVb += iVa;iVa = 0;}else{iVa -= (iConB - iVb);iVb = iConB;//iVa = iVa - (iConB - iVb);//这里错了，应该先计算iVa的值，因为iVb与iConB的值一样了，所以没有发生改变}
}int BFS(int s,int n,int m)
{int x,y,z;while(!queueStat.empty()){Stat stat = queueStat.front();queueStat.pop();x = stat.x;y = stat.y;z = stat.z;//从S倒向NDump(s,x,n,y);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}//重置初始状态，并进行状态更新x = stat.x;y = stat.y;z = stat.z;//从N倒向SDump(n,y,s,x);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}//重置初始状态，并进行状态更新x = stat.x;y = stat.y;z = stat.z;//从S倒向MDump(s,x,m,z);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}//重置初始状态，并进行状态更新x = stat.x;y = stat.y;z = stat.z;//从M倒向SDump(m,z,s,x);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}//重置初始状态，并进行状态更新x = stat.x;y = stat.y;z = stat.z;//从N倒向MDump(n,y,m,z);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}//重置初始状态，并进行状态更新x = stat.x;y = stat.y;z = stat.z;//从M倒向NDump(m,z,n,y);if(mark[x][y][z]==false){//进行剪枝mark[x][y][z] = true;//生成新状态Stat statNew;statNew.x = x;statNew.y = y;statNew.z = z;statNew.t = stat.t + 1;//判断是否达到平分状态if( (x==s/2 && y==s/2) || (x==s/2 && z==s/2) || (y==s/2 && z==s/2)){return statNew.t;}//没有达到平分状态，则放入队列中queueStat.push(statNew);}}//如果都没有找到，直接返回-1return -1;
}int main(int argc,char* argv[])
{int s,n,m;while(EOF!=scanf("%d %d %d",&s,&n,&m)){if(0==s){break;}//如果为奇数，不能平分，直接结束if(s%2==1){puts("NO");continue;}//将剪枝状态初始化为false;，//易错，并且要<=s，<=n,<=m,因为等于的状态也是需要考虑的//for(int i = 0 ; i < s ; i++)for(int i = 0 ; i <= s; i++){//for(int j = 0 ; j < n; j++)for(int j = 0;j <= n ;j++){for(int k = 0; k <= m ; k++)//for(int k = 0 ; k < m ; k++){mark[i][j][k] = false;}}}//初始化根节点状态Stat statRoot;statRoot.x = s;statRoot.y = 0;statRoot.z = 0;statRoot.t = 0;mark[s][0][0] = true;//易错，需要清空队列状态while(!queueStat.empty()){queueStat.pop();}queueStat.push(statRoot);int iRes = BFS(s,n,m);//printf("%d",iRes);if(-1==iRes){puts("NO");}else{printf("%d\n",iRes);}}system("pause");getchar();return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
