mc1.cpp

五子棋是一种受大众广泛喜爱的游戏

#include "stdio.h" 

//链表用于存储数据
struct INFO
{
     int nSavage;            //      岸边野人的数量 开始为3 全部到对岸为0
     int nBoanerges;         //      岸边传教士的数量 开始为3 全部到对岸为0
     int nSide;              //      船的位置 在左岸为-1 右岸为1
     int nMoveSavage;        //      渡河的野人的数量，用于递归时记录操作状态
     int nMoveBoanerges;     //      渡河的传教士的数量，用于递归时记录操作状态
     INFO* pPrevious;
     INFO* pNext;
};

     INFO* pHead = new INFO;


//计算阶乘
int factorial( int k)
{
	int i = 1;
	while( k>0 )
	{
		i = i*k;
		k--;
	}
	return i;
}


//判断是否有下一个满足条件的渡河方案
bool GetNextMove(INFO* pInfo)
{
     //      渡船的优先顺序
     //      此岸数量多优先，野人优先，彼岸数量少优先，传教士优先。
	 int kk = factorial( 3 );
     const int nStoreCount = 5;
	 //      存储渡河方案
     struct STORE
     {
           int nSavage;
           int nBoanerges;
     };

     STORE listStore[nStoreCount];

     if (pInfo->nSide == -1)	//左岸
     {
           listStore[0].nSavage = 2;
           listStore[0].nBoanerges = 0;

           listStore[1].nSavage = 1;
           listStore[1].nBoanerges = 1;

           listStore[2].nSavage = 0;
           listStore[2].nBoanerges = 2;

           listStore[3].nSavage = 1;
           listStore[3].nBoanerges = 0;

           listStore[4].nSavage = 0;
           listStore[4].nBoanerges = 1;
     }
     else
     {
           listStore[0].nSavage = 0;
           listStore[0].nBoanerges = 1;

           listStore[1].nSavage = 1;
           listStore[1].nBoanerges = 0;

           listStore[2].nSavage = 0;
           listStore[2].nBoanerges = 2;

           listStore[3].nSavage = 1;
           listStore[3].nBoanerges = 1;

           listStore[4].nSavage = 2;
           listStore[4].nBoanerges = 0;
     }

     int iStart;

     if (pInfo->nMoveSavage == 0 && pInfo->nMoveBoanerges == 0)
     {
           iStart = 0;
     }
     else
     {
           for (iStart=0; iStart<nStoreCount; iStart++)
           {
                 if (pInfo->nMoveSavage == listStore[iStart].nSavage && pInfo->nMoveBoanerges == listStore[iStart].nBoanerges)
                       break;
           }
           iStart++;
     }
     
     if (iStart < nStoreCount)
     {
           int i;
           for (i=iStart; i<nStoreCount; i++)
           {
                 int nSideSavage = pInfo->nSavage + listStore[i].nSavage * pInfo->nSide;
                 int nSideBoanerges = pInfo->nBoanerges + listStore[i].nBoanerges * pInfo->nSide;
                 int nBesideSavage = 3 - nSideSavage;
                 int nBesideBoanerges = 3 - nSideBoanerges;

                 //      传教士数量大于等于野人或为零
                 if ((nSideSavage<=nSideBoanerges || nSideBoanerges == 0) &&
                       (nBesideSavage<=nBesideBoanerges || nBesideBoanerges == 0) &&
                       nSideSavage>=0 && nSideBoanerges>=0 && nBesideSavage>=0 && nBesideBoanerges>=0)
                 {
                       //      如果本此解等于上次，放弃
                       if ( pInfo->pPrevious )
                       {
                             if (pInfo->pPrevious->nMoveBoanerges == listStore[i].nBoanerges &&
                                   pInfo->pPrevious->nMoveSavage == listStore[i].nSavage)
                             continue;
                       }
                       break;
                 }
           }
           if (i < nStoreCount)
           {
                 pInfo->nMoveSavage = listStore[i].nSavage;
                 pInfo->nMoveBoanerges = listStore[i].nBoanerges;
                 return true;
           }
     }

     return false;
}

int l=0;
//      递归函数
bool Ship(INFO* pInfo)
{
	l++;
	if (GetNextMove(pInfo))
	{
		INFO* pNew = new INFO;
		pNew->nSavage = pInfo->nSavage + pInfo->nMoveSavage * (pInfo->nSide);
		pNew->nBoanerges = pInfo->nBoanerges + pInfo->nMoveBoanerges * (pInfo->nSide);
		pNew->nSide = (pInfo->nSide) * (-1);
		pNew->pPrevious = pInfo;
		pNew->pNext = NULL;
		pNew->nMoveSavage = 0;
		pNew->nMoveBoanerges = 0;
		pInfo->pNext = pNew;
		if (pNew->nSavage == 0 && pNew->nBoanerges == 0)
		{
			printf("渡河过程如下：\n");
			INFO* pInfo = pHead;
			while (pInfo->pNext)
			{
				printf("渡河方向：%s 人数：野人%d - 传教士%d 此岸野人数：%d, 传教士数：%d\n", 
					(pInfo->nSide == -1) ? "-->" : "<--", pInfo->nMoveSavage, 
					pInfo->nMoveBoanerges, pInfo->nSavage, pInfo->nBoanerges);
				pInfo = pInfo->pNext;
			}
			printf("渡河完成。");
			if(l>=26)
				return true;      //      完成
			
		}
		return Ship(pNew);
	}
	else
	{
		INFO* pPre = pInfo->pPrevious;
		if (pPre == NULL) return false;            //      无解
		delete pInfo;
		pPre->pNext = NULL;
		return Ship(pPre);
	}
	return true;
}

int main(int argc, char* argv[])
{
     pHead->nSavage = 3;
     pHead->nBoanerges = 3;
     pHead->nSide = -1;
     pHead->pPrevious = NULL;
     pHead->pNext = NULL;
     pHead->nMoveSavage = 0;
     pHead->nMoveBoanerges = 0;

     if (Ship(pHead))
     {
/*         printf("渡河过程如下：\n");
           INFO* pInfo = pHead;
           while (pInfo->pNext)
           {
                 printf("渡河方向：%s 人数：野人%d - 传教士%d 此岸野人数：%d, 传教士数：%d\n", 
                       (pInfo->nSide == -1) ? "-->" : "<--", pInfo->nMoveSavage, 
                       pInfo->nMoveBoanerges, pInfo->nSavage, pInfo->nBoanerges);
                 pInfo = pInfo->pNext;
           }
           printf("渡河完成。");
*/
     }
     else
     {
           printf("此题无解！");
     }

     //      删除链表
     while (pHead)
     {
           INFO* pTemp = pHead->pNext;
           delete pHead;
           pHead=pTemp;
     }
     pHead = NULL;

     printf("请结束程序。");
     return 0;
}