riverproblem.cpp.bak

自己写的一个农夫,狼,羊,白菜过河问题的源代码.

///////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////


//Author:caobiao
//Email:[e-mail]
#include "stdio.h"
#include <iostream>
#include "malloc.h"
#include <list>
#define MAX_NUM    9
#define NULL 0
int DirectionNum = 0;
/*错误码定义*/
#define NO_ERROR                             0
#define MALLOC_ERROR                     	 1
#define NO_ANSWER                          	 2
#define SRCSTATE_DSTSTATE_SAME    	         3



enum PLACE
{
	NO,    // 没有过河的
	YES,   // 已经过河了
};


/*每一步都面临着八种选择*/
enum OPERATOR 
{
	MAN_GO,				 // 人过河
	MAN_GO_WITH_WOLF,	 // 人带狼过河
	MAN_GO_WITH_SHEEP,	 // 人带羊过河
	MAN_GO_WITH_MENU,	 // 人带菜过河
	MAN_BACK,			 // 人回来
	MAN_BACK_WITH_WOLF,	 // 人带狼回来
	MAN_BACK_WITH_SHEEP, // 人带羊回来
	MAN_BACK_WITH_MENU   // 人带菜回来
};


//人狼羊白菜的位置信息
typedef struct 
{
	PLACE PlaceState[4];//分别表示人狼羊白菜

}STATUS;

/*用来保存已经搜索过的状态*/
typedef struct GridExist
{
	STATUS status;
	OPERATOR Operation;
	GridExist *next;
	GridExist *parent;
}NineGridExist;

/*广度优先搜索队列需要保存的状态*/
typedef struct Stat
{
	STATUS status;
	OPERATOR Operation;
}GridState;

NineGridExist *GridExistHead = NULL;

int SaveExist(GridState State,GridState NextState)
{
	NineGridExist *p =		NULL;
	NineGridExist *q =		NULL;
	NineGridExist *r =		NULL;
	NineGridExist *parent =	NULL;

	int i = 0;
	if (NULL == GridExistHead)
	{
		GridExistHead = (NineGridExist *)malloc(sizeof(NineGridExist));
		if (NULL == GridExistHead)
		{
			return MALLOC_ERROR;
		}

		GridExistHead->next = NULL;
		GridExistHead->parent = NULL;
	    	GridExistHead->status = NextState.status;
		GridExistHead->Operation = NextState.Operation;

	}
	else
	{
		p = (NineGridExist *)malloc(sizeof(NineGridExist));
		if (NULL == p)
		{
			return MALLOC_ERROR;
		}
		for (q = GridExistHead; q ->next != NULL; q = q->next);
		q->next = p;

		p->status = NextState.status;
		p->Operation = NextState.Operation;

		for (r = GridExistHead; r != NULL; r = r->next)
		{
			if ((r->status.PlaceState[0] == State.status.PlaceState[0])
			&&  (r->status.PlaceState[1] == State.status.PlaceState[1])
			&&  (r->status.PlaceState[2] == State.status.PlaceState[2])
			&&  (r->status.PlaceState[3] == State.status.PlaceState[3]))
			{
				parent = r;
				break;
			}
		}
		p->parent = parent;
		p->next = NULL;
	}

	return NO_ERROR;
}


//////////////////////////////////////////////////////////////////////
//                             状态切换                             //
//////////////////////////////////////////////////////////////////////
bool StateChange(GridState State,OPERATOR Operation,GridState &NextState)
{
	switch (Operation)
	{
		case MAN_GO:
			if (NO == State.status.PlaceState[0])
			{
				NextState = State;
				NextState.status.PlaceState[0] = YES;
				NextState.Operation = Operation;	
				return true;
			}

		break;

		case MAN_GO_WITH_WOLF:
			if ((NO == State.status.PlaceState[0]) && (NO == State.status.PlaceState[1]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = YES;
				NextState.status.PlaceState[1] = YES;
				NextState.Operation = Operation;
				return true;
			}

		break;

		case MAN_GO_WITH_SHEEP:
			if ((NO == State.status.PlaceState[0]) && (NO == State.status.PlaceState[2]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = YES;
				NextState.status.PlaceState[2] = YES;
				NextState.Operation = Operation;	
				return true;
			}
		break;

		case MAN_GO_WITH_MENU:
			if ((NO == State.status.PlaceState[0]) && (NO == State.status.PlaceState[3]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = YES;
				NextState.status.PlaceState[3] = YES;
				NextState.Operation = Operation;
				return true;
			}
		break;

		case MAN_BACK:
			if (YES == State.status.PlaceState[0]) 
			{
				NextState = State;
				NextState.status.PlaceState[0] = NO;
				NextState.Operation = Operation;
				return true;
			}

		case MAN_BACK_WITH_WOLF:
			if ((YES == State.status.PlaceState[0]) && (YES == State.status.PlaceState[1]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = NO;
				NextState.status.PlaceState[1] = NO;
				NextState.Operation = Operation;
				return true;
			}
			break;

		case MAN_BACK_WITH_SHEEP:
			if ((YES == State.status.PlaceState[0]) && (YES == State.status.PlaceState[2]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = NO;
				NextState.status.PlaceState[2] = NO;
				NextState.Operation = Operation;
				return true;
			}
			break;
		
		case MAN_BACK_WITH_MENU:
			if ((YES == State.status.PlaceState[0]) && (YES == State.status.PlaceState[3]))
			{
				NextState = State;
				NextState.status.PlaceState[0] = NO;
				NextState.status.PlaceState[3] = NO;
				NextState.Operation = Operation;
				return true;
			}
			break;

		default:
		break;

	}
	return false;
}

/* 检查该状态是否已经存在*/
bool IfExist(GridState State)
{
	NineGridExist *r = NULL;
	for (r = GridExistHead; r != NULL; r = r->next)
	{
		if ((r->status.PlaceState[0] == State.status.PlaceState[0])
		&&  (r->status.PlaceState[1] == State.status.PlaceState[1])
		&&  (r->status.PlaceState[2] == State.status.PlaceState[2])
		&&  (r->status.PlaceState[3] == State.status.PlaceState[3]))
		{
			return true;
		}
	}
	return false;
}

/*检查该状态是否合法*/
bool StateTest(GridState State)
{
	if(State.status.PlaceState[0] != NO){
		if(State.status.PlaceState[1] == NO && State.status.PlaceState[2] == NO 
		|| State.status.PlaceState[2] == NO && State.status.PlaceState[3] == NO)
			return false;
	}
	if(State.status.PlaceState[0] != YES){
		if(State.status.PlaceState[1] == YES && State.status.PlaceState[2] == YES 
		|| State.status.PlaceState[2] == YES && State.status.PlaceState[3] == YES)
			return false;
	}

	return true;
}

/*判断问题是否已经求解*/
bool SuccessReach(GridState SrcState,GridState DstState)
{
	if ((SrcState.status.PlaceState[0] == DstState.status.PlaceState[0])
	&&  (SrcState.status.PlaceState[1] == DstState.status.PlaceState[1])
	&&  (SrcState.status.PlaceState[2] == DstState.status.PlaceState[2])
	&&  (SrcState.status.PlaceState[3] == DstState.status.PlaceState[3]))
	{
		return true;
	}
	return false;
}


/*打印路径*/
int PrintRoute(GridState SrcState,GridState DstState)
{
	std::list<GridState> m_iList;			
	std::list<GridState>::iterator m_iListItor;	

	NineGridExist *p = NULL;
	NineGridExist *q = NULL;
	GridState	TempState;
	int Step = 0;
	int Result = 0;
	GridState State ;
	for (p = GridExistHead; p != NULL; p = p->next)
	{
		if ((p->status.PlaceState[0] == DstState.status.PlaceState[0])
		&&  (p->status.PlaceState[1] == DstState.status.PlaceState[1])
		&&  (p->status.PlaceState[2] == DstState.status.PlaceState[2])
		&&  (p->status.PlaceState[3] == DstState.status.PlaceState[3]))
		{
			break;
		}
	}

	for (q = p; q != NULL; q = q->parent)
	{
		for (int i = 0; i < 4; i++)
		{
			TempState.status.PlaceState[i] = q->status.PlaceState[i];
		}
		TempState.Operation = q->Operation;
		m_iList.push_front(TempState);	
	}

	printf("人狼羊菜\n");

	int s = 1;
	while (m_iList.size()!=0) 
	{
		m_iListItor = m_iList.begin();
		TempState = *m_iListItor;	
		printf("%d %d %d %d",TempState.status.PlaceState[0],TempState.status.PlaceState[1],TempState.status.PlaceState[2],TempState.status.PlaceState[3]);
		printf("\n");
	

		m_iList.pop_front();
		Step++;
		s++;
	}
	printf("\nTotal Step:%d",Step - 1);
	printf("\n");

	return NO_ERROR;
}


/*广度优先搜索主函数*/
int Route(GridState SrcState,GridState DstState)
{
	std::list<GridState> m_iList;			
	std::list<GridState>::iterator m_iListItor;	
	GridState State ;
	GridState Nextstate;
	int Result = 0;

	//入队列
	m_iList.push_back(SrcState);

	Result = SaveExist(SrcState,SrcState);
	if (Result != NO_ERROR)
	{
		return Result;
	}

	if (SuccessReach(SrcState,DstState))
	{
		return SRCSTATE_DSTSTATE_SAME;
	}

	while (m_iList.size()!=0) 
	{
		m_iListItor = m_iList.begin();
		State = *m_iListItor;	
		m_iList.pop_front();//出队列

		for (OPERATOR Oper = MAN_GO; Oper <= MAN_BACK_WITH_MENU; Oper = (OPERATOR)(Oper+1))
		{
			if (StateChange(State,Oper,Nextstate))
			{
				if (StateTest(Nextstate))
				{
					Result = SaveExist(State,Nextstate);
					if (Result != NO_ERROR)
					{
						return Result;
					}
					
					if (SuccessReach(Nextstate,DstState))
					{
						Result = PrintRoute(SrcState,DstState);
						if (Result != NO_ERROR)
						{
							return Result;
						}
						else
						{
							return NO_ERROR;
						}
					}
					else
					{
						m_iList.push_back(Nextstate);
					}
				}
			}
		}
	}

	return NO_ANSWER;
}

void Debug_printf(int Result)
{
	switch(Result)
	{
		case MALLOC_ERROR:
		printf("\n Malloc Error!\n");
		break;
		
		case NO_ANSWER:
		printf("\nNo Answer!\n");
		break;

		case SRCSTATE_DSTSTATE_SAME:
		printf("\nSrcState and DstState are same!\n");
		break;
	
		default:
		printf("\nUnKnow Error!");
		break;
	}
}

void main()
{
	int i = 987654321;
	GridState SrcState;
	GridState DstState;

	for (int i = 0; i < 4; i++)
	{	SrcState.status.PlaceState[i] = NO;
		DstState.status.PlaceState[i] = YES;
	}

	int Result = 0;

	Result = Route(SrcState,DstState);
	if (NO_ERROR != Result)
	{
		Debug_printf(Result);
		
	}
	getchar();
	printf("\n");
}