#include<stdio.h>

typedef struct Boat         /// 船結(jié)構(gòu)，即表示船上野蠻人和傳教士的個(gè)數(shù)
{
	int numX;               /// 傳教士個(gè)數(shù)
	int numY;               /// 野蠻人個(gè)數(shù)
}Boat;

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

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

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

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