算法竞赛入门经典：第七章 暴力求解法 7.18倒水问题

/*
倒水问题：
有装满水的6升杯子、空的3升杯子和一升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢?
输入:
6（满杯水所在的刻度） 3 1
输出:
(6,0,0)->(3,3,0)->(3,2,1)->(4,2,0)

思路：
这与倒可乐是一个问题，关键在与状态的搜索。
1 采用广度优先搜索算法
2 当前状态的下一状态的方法为:(a,b,c)
状态：全部分
*/

/*
关键：
1 小杯子倒向大杯子，只能全部倒入。大杯子倒向小杯子，把大杯子加满。
2 需要使用倾倒函数。量出4升水的方法是:3升杯装中装2升，1升杯0升，6升杯中为4升。
3 如何打印状态，需要在状态中设置访问标记。设置一个父节点指针，到时候逆向打印即可
4 迷宫是无向图，倒水是有向状态图

*/

#include <stdio.h>
#include <stdlib.h>
#include <queue>

#define MAXSIZE 1024

using namespace std;

typedef struct Stat
{
	Stat(int a,int b,int c,int d,Stat* s):x(a),y(b),z(c),t(d),par(s){}
	int x;//6升杯中容量
	int y;//3升杯中容量
	int z;//1升杯中容量
	int t;//倾倒次数
	Stat* par;
	//int v;//访问标记，1表示访问
}Stat;

queue<Stat> queueStat;
queue<Stat> printStat;
Stat endStat(0,0,0,0,NULL);
//int iCapA,iCapB,iCapC;//3个容器的容量

void dump(int iConA,int& iVa,int iConB,int& iVb)//A容器中的水倒向B容器中的水
{
	if(iVa > iConA || iVb > iConB || iVa < 0 || iVb <0)//合法性检验
	{
		return;
	}
	if(iVa + iVb < iConB)//A容器小于B容器，应该加满B
	{
		iVb += iVa;
		iVa = 0;
	}
	else
	{
		iVa -= iConB - iVb;
		iVb = iConB;	
	}
}

int  dfs(int iCapA,int iCapB,int iCapC)//当前3个杯子中水的容量
{
	int x,y,z,t;
	while(!queueStat.empty())
	{
		Stat stat = queueStat.front();
		queueStat.pop();

		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		//a向b倾倒
		dump(iCapA,x,iCapB,y);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat(x,y,z,t+1,&stat);//如果是这样的话，应该保存的是new出来的节点，而且应该保存最后一个状态
		queueStat.push(newStat);
		printStat.push(newStat);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat;
			return(t+1);
		}
		else//没找到，生成新状态
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}

		//a向c倾倒
		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		dump(iCapA,x,iCapC,z);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat2(x,y,z,t+1,&stat);
		queueStat.push(newStat2);
		printStat.push(newStat2);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat2;
			return(t+1);
		}
		else//没找到，生成新状态
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}

		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		//b向a倾倒
		dump(iCapB,y,iCapA,x);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat3(x,y,z,t+1,&stat);
		queueStat.push(newStat3);
		printStat.push(newStat3);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat3;
			return(t+1);
		}
		else//没找到，生成新状态
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}

		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		//b向c倾倒
		dump(iCapB,y,iCapC,z);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat4(x,y,z,t+1,&stat);
		queueStat.push(newStat4);
		printStat.push(newStat4);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat4;
			return(t+1);
		}
		else//没找到，生成新状态
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}

		//c向a倾倒
		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		dump(iCapC,z,iCapA,x);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat5(x,y,z,t+1,&stat);
		queueStat.push(newStat5);
		printStat.push(newStat5);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat5;
			return(t+1);
		}
		else//没找到，生成新状态
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}

		//c向b倾倒
		x = stat.x;
		y = stat.y;
		z = stat.z;
		t = stat.t;
		dump(iCapC,z,iCapB,y);
		if(x < 0 || x > iCapA || y < 0 || y > iCapB || z < 0 || z > iCapC )
		{
			continue;
		}
		Stat newStat6(x,y,z,t+1,&stat);
		queueStat.push(newStat6);
		printStat.push(newStat6);
		if(x == 4 && y == 2 && z == 0)//如果找到，就直接退出
		{
			endStat = newStat6;
			return(t+1);
		}
		else//没找到，生成新状态,一定要剪枝
		{
			//Stat newStat(x,y,z,t+1);
			//queueStat.push(newStat);
			//printStat.push(newStat);
		}
	}
	return -1;
}

void print(Stat curStat)
{
	if(curStat.par == NULL)//递归出口
	{
		return;
	}
	else
	{
		Stat parStat = *curStat.par;
		print(parStat);
		printf("(%d,%d,%d) ",parStat.x,parStat.y,parStat.z);
	}
}

int main(int argc,char* argv[])
{
	int a,b,c;
	while(EOF != scanf("%d %d %d",&a,&b,&c))
	{
		Stat begStat(a,0,0,0,NULL);
		queueStat.push(begStat);
		printStat.push(begStat);
		int iRes = dfs(a,b,c);
		printf("%d\n",iRes);
		print(endStat);
	}
	system("pause");
	return 0;
}