//修道士與野人問題
//這是一個古典問題。假設有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  <--- 野人分布


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

*/