savageacrosstheriver.cpp

假设有N个修道士和N个野人准备渡河

//修道士与野人问题
//这是一个古典问题。假设有N个修道士和N个野人准备渡河，但只有一天能容纳C人的小船，
//为了防止野人吃掉修道士，要求无论在何处（即两岸、船上），修道士的人数不得少于野
//人的人数（除非修道士人数为0）。如果两种人都会划船，试设计一个程序，确定他们能
//否渡过河去，若能，则给出一个小船来回次数最少的最佳方案，并打印出船来回的状态及
//野人和修道士人数变化状态。


// 3.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#define States_MAX 1000000  //数组M[][6]第0维的最大维数,不能超过
#define Stack_Stack1_MAX 100000

/////////////////////////////////////////////////////////////////////////////////////////////
// 产生所有和平共处的合法状态到数组M[][6],状态个数放在全局变量Num中
//
// 状态意义如下:
//
//     左岸  |  船   |    右岸
//      i    |  j    |     k      <-----人的数目    
//     ------+-------+------------ 
//      l    |  m    |     n      <-----野人的数目
//
//N为人和野人各自总数,C为船上最多人数
int CreateAllValidStates(short int M[][6],int N,int C) 
{
	int i,j,k,l,m,n,Num = 0;

	//产生所有人和野人在三个位置的可能个数,对所有可能组合进行搜索
	for(i=0;i<=N;++i)
	for(j=0;j<=C;++j)
	for(l=0;l<=N;++l)
	for(m=0;m<=C-j;++m)
	{
		k = N-i-j;
		n = N-l-m;

		//满足下列条件,则人和野人可以和平共处,把对应的人数i,j,k和野人数l,m,n记入数组M[][6]中
		if( k>=0 && n>=0 && (i>=l||i==0) && (k>=n||k==0) && 
			(j>=m||j==0) && i+j+k == N && m+n+l == N && 
			(m+j>=1||m+j==0 && (k==N&&n==N || i==N && l==N) ) )
		{
			M[Num][0] = i;
			M[Num][1] = j;
			M[Num][2] = k;
			M[Num][3] = l;
			M[Num][4] = m;
			M[Num][5] = n;
			++Num;                    //合法状态数加1
			
			if( Num >= States_MAX )   //防止数组越界
				return Num;           //返回所有合法状态总数目
		}
	}

	return Num; //返回所有合法状态总数目
}

//////////////////////////////////////////////////////////////////////////////////////
//满足这一条件则表示状态结点s1[]和s2[]是相邻的,即可以通过船从状态s1[]变到状态s2[]上
// 状态意义如下:  二个状态结点,作为有向图的顶点
//
//     左岸  |  船   |    右岸          左岸  |  船   |    右岸
//     s1[0] | s1[1] |    s1[2]         s2[0] | s2[1] |    s2[2]     <-----人的数目    
//     ------+-------+------------      ------+-------+------------ 
//     s1[3] | s1[4] |    s1[5]         s2[3] | s2[4] |    s2[5]     <-----野人的数目
//
//如果函数返回1,则存在一条从顶点s1到顶点s2的有向边, 即通过一次渡船,可以从顶点s1的状态
//变到顶点s2的状态
bool s1_to_s2(short int s1[],short int s2[])
{
	if( ( s1[0] == s2[0] && s1[3]==s2[3]  &&              //二结点左边人数和左边野人数分别相等
		  (s1[1]+s1[2]>=s1[4]+s1[5]||s1[1]+s1[2]==0) ) || //右岸到岸时也要和平共处
		( s1[2] == s2[2] && s1[5]==s2[5]  &&               //二结点右边人数和右边野人数分别相等
		  (s1[0]+s1[1]>=s1[3]+s1[4]||s1[0]+s1[1]==0) ) )  //左岸到岸时也要和平共处
		return 1; 

	return 0;     //二种状态结点之间没有直接关系,不能通过船来转换,图上这二状态结点之间没有有向边
}

void Get_Start_End_Index(short int M[][6],int Num,int N,int *Start_Node_Idx,int *End_Node_Idx)
{
	int i;

	for(i=0;i<Num;++i)
	{
		if(M[i][0] == N && M[i][3] == N)
		{	
			*Start_Node_Idx = i; //找到开始下标
		}
		if(M[i][2] == N && M[i][5] == N)
		{	
			*End_Node_Idx = i;  //找到结束下标
		}
	}
}

//////////////////////////////////////////////////////////////////////////////////
//广度优先遍历,从下标Start_Node_Idx的顶点出发到碰到下标为End_Node_Idx的顶点为止,
//输出所遍历的各状态顶点,
//如果没有,则输出失则信息.
int Stack[Stack_Stack1_MAX];  //遍历栈,放顶点在M[][6]中的下标
int Stack1[Stack_Stack1_MAX]; //记录路径历史:Stack中对应下标顶点的前趋顶点下标
char  Flag[States_MAX];       //图的广度优先遍历存放结点是否已访问过的标志 

void BreadthFirstSearch_From_StartNode_To_EndNode(
	short int M[][6],int Num,int Start_Node_Idx,int End_Node_Idx)
{
	int Top; //栈顶

	//为广度优先对状态结点的访问过标志设置成0,表示状态结点未访问过
	for(int i=0;i<States_MAX;++i)
		Flag[i] = 0;

	//从Start出发广度优先遍历找到End的最短路径
	Stack[1] = Start_Node_Idx; //栈初始化,起始下标入栈,栈底是从1开始的
	Flag[Start_Node_Idx] = 1;  //起始点设成1,表示已访问过
	Top = 2;                   //栈顶置初值,

	Stack1[0] = -1;            //记录路径历史,以便以后输出整个路径,-1是结束标志
	Stack1[1] = 0;    //置成 0,则下回 Stack1[0] ==-1就可结束路径输出,这是为do_while循环控制方便设置的

	int b1 = 1;       //广度搜索时,前一个前趋顶点的下标置初值,
	int kk,vv;        //二个循环用中间变量

	while(1)
	{
		for( kk=0; kk<Num; ++kk) //在所有结点中找到后继顶点
		{
			if(Flag[kk]==1) continue; //在所有未初访问过的状态结点里查找相邻状态结点

			if(s1_to_s2(M[Stack[b1]],M[kk])) //满足这一条件则表示状态结点M[Stack[b1]]和M[kk]是相邻的,即可以通过船从状态M[Stack[b1]]变到状态M[kk]上
			{
				Flag[kk] = 1;     //设访问过标志
				Stack[Top] = kk;  //下标入栈
				Stack1[Top] = b1; //前一个遍历的结点的下标入历史栈
				++Top;
				
				//如果已到结束顶点,则打印从开始顶点到结束顶点路径上的各顶点的状态值
				if( kk == End_Node_Idx ) 
				{
					//根据遍历的路径的跟踪记录,反向顺序输出所走过的状态结点路径
					vv = Top-1;

					printf("\n状态输出\n\n\n  左岸|   船 |  右岸\n");
					do
					{
						printf("\n%5d |%5d |%5d  <--- 人分布\n%5d |%5d |%5d  <--- 野人分布\n",
							M[Stack[vv]][0],M[Stack[vv]][1],M[Stack[vv]][2],
							M[Stack[vv]][3],M[Stack[vv]][4],M[Stack[vv]][5]);
						
						vv = Stack1[vv];	
					}while(Stack1[vv]!=-1);
					
					printf("\n\n根据以上各分布,从下到上容易得到船每次是怎么渡人和野人的.\n\n");

					return;
				}
			}
		}//for(kk...)
		
		++b1;
		if(b1==Top) 
		{
			printf("=== 失败,找不到渡河方案 ===");//不可能渡过去
			return;
		}
	}//while(1)
}


//存放所有和平共处状态值的顶点
short int States[States_MAX][6];          

void main()
{
	int N,C,Num;
	
	printf("输入人数 N 和 船可容人数 C : ");
	scanf("%d%d",&N,&C);

	//产生所有和平共处状态值的顶点到States中,返回状态总数到Num
	Num = CreateAllValidStates(States,N,C);
	printf("所产生的总状态结点数: %d.\n",Num);	
	
	//得到起始顶点和终止顶点下标
	int Start_Node_Idx; //存放在States[][6]找到的开始状态(N个人和野人都在左岸)下标
	int End_Node_Idx;   //存放在States[][6]找到的结束状态(N个人和野人都渡到右岸)下标
	Get_Start_End_Index(States,Num,N,&Start_Node_Idx,&End_Node_Idx);

	//广度优先遍历,从下标Start_Node_Idx的顶点出发到碰到下标为End_Node_Idx的顶点为止,
	//输出所遍历的各状态顶点,
	//如果没有,则输出失则信息.
	BreadthFirstSearch_From_StartNode_To_EndNode(States,Num,Start_Node_Idx,End_Node_Idx);
}


//========注意=============
//如果运行时前面的输出已经越出屏幕
//则可以在DOS下运行,在EXE程序目录下打入
// 3 >> out.txt
//再打开out.txt即可查看
//如果是Windows XP 或Windows 2000,2003,则可以全选后
//用Ctrl_Insert复制到剪切板上,再粘贴.
/*
一个运行例子:


输入人数 N 和 船可容人数 C : 5  3 

所产生的总状态数: 99.

状态输出


  左岸|   船 |  右岸

    0 |    0 |    5  <--- 人分布
    0 |    0 |    5  <--- 野人分布

    0 |    0 |    5  <--- 人分布
    0 |    2 |    3  <--- 野人分布

    0 |    0 |    5  <--- 人分布
    1 |    1 |    3  <--- 野人分布

    0 |    0 |    5  <--- 人分布
    1 |    3 |    1  <--- 野人分布

    0 |    0 |    5  <--- 人分布
    3 |    1 |    1  <--- 野人分布

    0 |    3 |    2  <--- 人分布
    3 |    0 |    2  <--- 野人分布

    2 |    1 |    2  <--- 人分布
    2 |    1 |    2  <--- 野人分布

    2 |    3 |    0  <--- 人分布
    2 |    0 |    3  <--- 野人分布

    5 |    0 |    0  <--- 人分布
    1 |    1 |    3  <--- 野人分布

    5 |    0 |    0  <--- 人分布
    1 |    3 |    1  <--- 野人分布

    4 |    1 |    0  <--- 人分布
    4 |    0 |    1  <--- 野人分布

    4 |    1 |    0  <--- 人分布
    4 |    1 |    0  <--- 野人分布

    5 |    0 |    0  <--- 人分布
    5 |    0 |    0  <--- 野人分布


根据以上各分布变化,从下到上容易得到船每次是怎么渡人和野人的.

*/