water_p.cpp

分水问题

// water.c : Defines the entry point for the console application.
//int solve(State s, SqList path)
// 求一个解
// 该程序被书采用
#include <stdio.h>
#include <stdlib.h>
/*
typedef struct{
	int a;
	int b;
}State;
//typedef State ElemType;


#define A 5
#define B 3
#define C 4
*/
#include "seqlist.h"
int A, B, C;

//int goal(State s);
//void findnexts(State s, SqList* nexts);
//void printpath(SqList path);
//int solve(State s, SqList path);
//int EQ(State e1,State e2);

int EQ(State e1,State e2){
	if((e1.a==e2.a)&&(e1.b==e2.b))
		return 1;
	else
		return 0;
}


void findnexts(State s, SqList &nexts)
{
	State tmp;

	//full A
	if (s.a != A) {
		tmp.a = A;
		tmp.b = s.b;
		ListAppend_Sq(nexts,tmp);
	}

	//full B
	if (s.b != B) {
		tmp.b = B;
		tmp.a = s.a;
		ListAppend_Sq(nexts,tmp);
	}

	//empty A
	if (s.a) {
		tmp.a = 0;
		tmp.b = s.b;
		ListAppend_Sq(nexts,tmp);
	}

	//empty B
	if (s.b) {
		tmp.b = 0;
		tmp.a = s.a;
		ListAppend_Sq(nexts,tmp);
	}

	//A to B
	if (s.a && (s.b != B)) {
		int d = B - s.b;
		if (s.a >= d) {
			//full B from A
			tmp.a = s.a - d;
			tmp.b = B;
		}
		else {
			//empty A by B
			tmp.a = 0;
			tmp.b = s.b + s.a;
		}
		ListAppend_Sq(nexts,tmp);
	}

	//B to A
	if (s.b && (s.a != A)) {
		int d = A - s.a;
		if (s.b >= d) {
			//full A from B
			tmp.b = s.b - d;
			tmp.a = A;
		}
		else {
			//empty B by A
			tmp.b = 0;
			tmp.a = s.a + s.b;
		}
		ListAppend_Sq(nexts,tmp);
	}
}

int is_goal(State s,int goad)
{
	return (s.a == goad) || (s.b == goad) || (s.b + s.a == goad);
}

void printpath(SqList &path)
{
	int i;
	State tmp;
	for (i=1; i <=ListLength_Sq(path); i++) {
	    GetElem_Sq(path,i,tmp);
	    printf(" (");printf("%d",tmp.a);printf(",");printf("%d",tmp.b);printf(")");
	}
}

int water(State s, int goad,SqList path)
{//本算法求从s到达目标goad的一个解

	SqList nexts;
	State next;
	int i;
	ListAppend_Sq(path,s);
	if(is_goal(s,goad))// 
	{
		printf("\n\n a solution is:");
		printpath(path);
		return 1;
	}
	InitList_Sq(nexts);
	findnexts(s, nexts);////求得当前状态的所有下一步状态
	for(i = 1; i <=ListLength_Sq(nexts); i++)////依次处理当前状态的下一步状态
	{
		GetElem_Sq(nexts,i,next);
		if(!LocateElem_Sq(path,next, EQ))//若下一步状态不在当前路径上
		  if(water(next,goad,path)) return 1;//求从next到达目标goad的一个解
	}
	return 0;
}

void main()
{
	State start;
	SqList path;
	InitList_Sq(path);
	printf("\n\n A :");
	scanf("%d", &A);
	printf("\n B :");
	scanf("%d", &B);
	printf("\n C :");
	scanf("%d", &C);
    start.a = 0;
	start.b = 0;
	if (!water(start,C,path))
		printf("\n\n sorry, no solution");
	DestroyList_Sq(path);
	printf("\n\n");
}