#include<stdio.h>

typedef struct Boat         /// 船結構，即表示船上野蠻人和傳教士的個數
{
	int numX;               /// 傳教士個數
	int numY;               /// 野蠻人個數
}Boat;

Boat LtoR[3]={{2,0},{0,2},{1,1}};    ///從左岸到右岸時船上裝的人的種類，有3種
                                  ///2個野人和0個傳教士，0個野人和2個傳教士，1個野人和1個傳教士
Boat RtoL[2]={{1,0},{0,1}};       ///從右岸回左岸時船上裝人的種類，有2種
                                  ///1個野人或1個傳教士

int fnPassRiver1(x1,y1,x2,y2);     ///遞歸函數，表示每次由一個野蠻人駕船從右岸回左岸
int fnPassRiver2(x1,y1,x2,y2);     ///遞歸函數，表示每次由一個傳教士駕船從右岸回左岸

main()
{
	int x1,y1,x2,y2;    
	///  x1左岸野蠻人個數，y1左岸傳教士個數；x2右岸野蠻人個數，y2右岸傳教士個數
    int k;
    printf("      左岸                  右岸                 船上 \n");
    printf("野蠻人    傳教士      野蠻人    傳教士    野蠻人     傳教士\n");
	
	///三重循環，表示第一次去右岸時，船上人數的種類，即數組LtoR[3]的三種情況
	for(k=0;k<3;k++)        
	{   x1=3,x2=0,y1=3,y2=0;
	    
    	switch(k)
		{	
		case 0 : printf("-------------------------第一次兩個野蠻人先過河-------------------\n");
			break;
        case 1 : printf("\n-----------------------第二次兩個傳教士先過河-------------------\n");
			break;
		case 2 : printf("\n-----------------第三次一個野蠻人和一個傳教士一起過河-----------\n");
		    break;
		default:
			break;
		}
		printf("  %d         %d          %d        %d    \n\n",x1,y1,x2,y2);
		
		x1-=LtoR[k].numX;              ////第一次去右岸后，岸兩邊人數變化情況
		y1-=LtoR[k].numY;
		x2+=LtoR[k].numX;
		y2+=LtoR[k].numY;
	    fnPassRiver1(x1,y1,x2,y2);     ///調用遞歸函數過河
		fnPassRiver2(x1,y1,x2,y2);     ///調用遞歸函數過河
	}
}

int fnPassRiver1(xx1,yy1,xx2,yy2)      ///表示每次由一個野蠻人駕船從右岸回左岸后，再向右過河的過程      
{ 
  int x1,y1,x2,y2;
  int i,j;
  x1=xx1;y1=yy1;x2=xx2;y2=yy2;
  printf("  %d         %d          %d        %d    \n",x1,y1,x2,y2);
 // getch(); 
  
  if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)       /////錯誤返回上一級遞歸函數
  {printf("wrong!!!             錯誤類型：理論上的人數出現負數 ，搜索過程錯誤\n");
   return 0;
  }
  else if(((x1>y1)&&y1!=0)||((x2>y2)&&y2!=0))              /////錯誤返回上一級遞歸函數
  {printf("wrong!!!             錯誤類型：野蠻人的個數大于傳教士的個數\n");
   return 0;
  }
  else if(x1==0&&y1==0&&x2==3&&y2==3)                      /////成功返回上一級遞歸函數
  {printf("seccessful!!!               過河成功\n");
   return 0; 
  }
  else 
  {  
	      x2-=1;                     ///  一個野蠻人駕船回左岸，則右岸野蠻人個數減一
		  y2-=0;                     ///  右岸傳教士個數不變
		                             ///  此時人在船上，左岸人數，即x1,y1暫時不作調整 
		  if(x2<0||y2<0)   return 0;
		  
          ///當一個野人駕船回左岸后帶上另一個野人回右岸，調用下一級遞歸函數
		  fnPassRiver1(x1-1,y1,x2+2,y2);
		  printf("類型11        \n  %d         %d          %d        %d           %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
		  
		  ///當一個野人駕船回左岸后帶上一個傳教士回右岸，調用下一級遞歸函數
          fnPassRiver1(x1,y1-1,x2+1,y2+1);
		  printf("類型22        \n  %d         %d          %d        %d           %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
          
		  ///當一個野人駕船回左岸后此野人下船，同時另外兩個傳教士上船回右岸，調用下一級遞歸函數
		  fnPassRiver1(x1+1,y1-2,x2,y2+2);
		  printf("類型33        \n  %d         %d          %d        %d           %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch(); 
           
		  return 0;
  }
}

int fnPassRiver2(xx1,yy1,xx2,yy2)      ///表示每次由一個傳教士駕船從右岸回左岸后,再向右過河的過程   
{ 
  int x1,y1,x2,y2;
  int i,j;
  x1=xx1,y1=yy1,x2=xx2,y2=yy2;
  printf("  %d         %d          %d        %d \n",x1,y1,x2,y2); 
  getch(); 
  
  if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)     /////錯誤返回上一級遞歸函數
  {printf("wrong!!!             錯誤類型：理論上的人數出現負數 ，搜索過程錯誤\n");
   return 0;
  }
  else if(((x1>y1)&&y1!=0)||((x2>y2)&&y2!=0))            /////錯誤返回上一級遞歸函數
  {printf("wrong!!!             錯誤類型：野蠻人的個數大于傳教士的個數\n");
   return 0;
  }
  else if(x1==0&&y1==0&&x2==3&&y2==3)                    /////成功返回上一級遞歸函數
  {printf("seccessful!!!               過河成功\n");
   return 0; 
  }
  else 
  {  
	      x2-=0;                      ///  一個傳教士駕船回左岸，則右岸傳教士個數減一
		  y2-=1;                      ///  右岸野蠻人個數不變
		                              ///  此時人在船上，左岸人數，即x1,y1暫時不作調整 
		  
		  if(x2<0||y2<0) return 0;
          
		  ///當一個傳教士駕船回左岸后帶上另一個傳教士回右岸，調用下一級遞歸函數
          fnPassRiver2(x1,y1-1,x2,y2+2);
	      printf("類型44        \n  %d         %d          %d        %d        %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
          
		  ///當一個傳教士駕船回左岸后帶上一個野人回右岸，調用下一級遞歸函數
		  fnPassRiver2(x1-1,y1,x2+1,y2+1);
          printf("類型55        \n  %d         %d          %d        %d        %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();	
          
		  ///當一個傳教士駕船回左岸后此傳教士下船，同時另外兩個野人上船回右岸，調用下一級遞歸函數
		  fnPassRiver2(x1-2,y1+1,x2+2,y2);
		  printf("類型66        \n  %d         %d          %d        %d        %d        %d\n",x1,y1,x2,y2,3-x1-x2,3-y1-y2);
          getch();
	
		  return 0;	
  }
}