main.cpp

经典的青蛙过河游戏的外挂算法,使用 C 兼容编译编译通过

#include "stdio.h"
#include "memory.h"


#define   LTR_ONE			1
#define   LTR_TWO			2         
#define   RTL_ONE			3
#define   RTL_TWO			4
#define   LTR_ONE_OFFSET    1
#define   LTR_TWO_OFFSET    2 
#define   RTL_ONE_OFFSET    -1
#define   RTL_TWO_OFFSET	-2

#define   STATUS_MAX_LEN    21
#define   INVALID_ARR_LOC	0xff
#define   MAX_STACK_SIZE	0x400



char			szStatusBuf[STATUS_MAX_LEN];
unsigned long	lpStack[MAX_STACK_SIZE];
unsigned long	pCurPoint = 0;
int				nLen;


bool IsPass(char* szCurStatus);
void SwapChr(char* s1,char* s2);
int GetSpaceByteLoc(char* szCurStatus);
bool SetStatusFun(char* szCurStatus,int nStatus);
bool MyRecurFun(char* szCurStatus);
void DispRel();
void DispBuf(char* szBuf,int nLen);


void main()
{
	bool bTmp;
	int  i, nCnt = 0;

	printf("请输入青蛙的数目(6 - 20 间的偶数):\n\n");
	
	scanf("%d",&nCnt);
	if (nCnt & 0x00000001)
		return;
	if ((nCnt < 6)||(nCnt > 20))
		return;

	nLen = nCnt + 1;
	for (i = 0;i<nLen;i++)
	{
		if (i<(nLen/2))
			szStatusBuf[i] = i+1;
		else if (i == (nLen/2))
			szStatusBuf[i] = 0;
		else
			szStatusBuf[i] = i;
			
	}
	memset(lpStack,0,nLen*sizeof(unsigned long));
	MyRecurFun(szStatusBuf);

	


}

bool MyRecurFun(char* szCurStatus)
{
	bool	bPass,bRel = false;
	char	szTmp[STATUS_MAX_LEN];


	bPass = IsPass(szCurStatus);
	if (bPass)
	{
		bRel = true;
		goto MyExit;
	}

	memcpy(szTmp,szCurStatus,nLen);
	if (SetStatusFun(szTmp,LTR_ONE))
	{
		lpStack[pCurPoint] = LTR_ONE;
		pCurPoint++;
		MyRecurFun(szTmp);
		pCurPoint--;
	}

	memcpy(szTmp,szCurStatus,nLen);
	if (SetStatusFun(szTmp,LTR_TWO))
	{
		lpStack[pCurPoint] = LTR_TWO;
		pCurPoint++;
		MyRecurFun(szTmp);
		pCurPoint--;
	}
	
	memcpy(szTmp,szCurStatus,nLen);
	if (SetStatusFun(szTmp,RTL_ONE))
	{
		lpStack[pCurPoint] = RTL_ONE;
		pCurPoint++;
		MyRecurFun(szTmp);
		pCurPoint--;
	}
	
	memcpy(szTmp,szCurStatus,nLen);
	if (SetStatusFun(szTmp,RTL_TWO))
	{
		lpStack[pCurPoint] = RTL_TWO;
		pCurPoint++;
		MyRecurFun(szTmp);
		pCurPoint--;
	}
	
MyExit:
	if (bPass)
	{
		DispBuf(szCurStatus,nLen);
		DispRel();
	}
	return  bRel;
}

bool SetStatusFun(char* szCurStatus,int nStatus)
{
	int     nSpaceLoc,nHalfNum;
	bool	bRel = false;

	nSpaceLoc = GetSpaceByteLoc(szCurStatus);
	if (nSpaceLoc == INVALID_ARR_LOC)
		return false;
	
	nHalfNum = nLen/2;

	switch(nStatus)
	{
	case LTR_ONE:			//空位往右搬移1个位置
		if (szCurStatus[nSpaceLoc+LTR_ONE_OFFSET]<=nHalfNum) // 不符合规则不能交换
		{
			bRel = false;
			break;
		}
		SwapChr(&szCurStatus[nSpaceLoc],&szCurStatus[nSpaceLoc+LTR_ONE_OFFSET]);
		bRel = true;
		break;
	case LTR_TWO:			//空位往右搬移2个位置
		if (szCurStatus[nSpaceLoc+LTR_TWO_OFFSET]<=nHalfNum) // 不符合规则不能交换
		{
			bRel = false;
			break;
		}
		SwapChr(&szCurStatus[nSpaceLoc],&szCurStatus[nSpaceLoc+LTR_TWO_OFFSET]);
		bRel = true;
		break;
	case RTL_ONE:			//空位往左搬移1个位置
		if (szCurStatus[nSpaceLoc+RTL_ONE_OFFSET]>nHalfNum) // 不符合规则不能交换
		{
			bRel = false;
			break;
		}
		SwapChr(&szCurStatus[nSpaceLoc],&szCurStatus[nSpaceLoc+RTL_ONE_OFFSET]);
		bRel = true;
	    break;
	case RTL_TWO:			//空位往左搬移2个位置
		if (szCurStatus[nSpaceLoc+RTL_TWO_OFFSET]>nHalfNum) // 不符合规则不能交换
		{
			bRel = false;
			break;
		}
		SwapChr(&szCurStatus[nSpaceLoc],&szCurStatus[nSpaceLoc+RTL_TWO_OFFSET]);
		bRel = true;
	    break;
	default:
		bRel = false;
	    break;
	}
	
	return bRel;

}

//是否已经通关
bool IsPass(char* szCurStatus)
{
	int		i,nHalfNum;
	char	cTmp1;

	for (i = 0; i<nLen;i++ )
	{	
		nHalfNum = nLen/2;
		cTmp1 = szCurStatus[i] - 1;
		
		if (i<nHalfNum)
		{
			if (cTmp1 < nHalfNum)
				return false;	
		}
		else if (i == nHalfNum)
		{	
			if ((cTmp1+1) != 0)
				return false;
		}
		else
		{
			if((cTmp1+1) > nHalfNum)
				return false;
		}
	}
	
	return true;
}

//获取空位
int GetSpaceByteLoc(char* szCurStatus)
{
	int i,nRel = INVALID_ARR_LOC;
	
	for (i = 0;i<nLen; i++)
	{
		if (!szCurStatus[i])
		{
			nRel = i;
			break;
		}
		
	}

	return nRel;
}

//交换字节
void SwapChr(char* s1,char* s2)
{
	char cTmp;
	cTmp = *s1;
	*s1 = *s2;
	*s2 = cTmp;
}

//显示结果
void DispRel()
{
	unsigned long i;
	char szTmp[STATUS_MAX_LEN];
	bool bTest;

	memcpy(szTmp,szStatusBuf,nLen);
	DispBuf(szTmp,nLen);


	for (i=0;i<pCurPoint;i++)
	{
		bTest = SetStatusFun(szTmp,lpStack[i]);
		DispBuf(szTmp,nLen);
	}
	
}

void DispBuf(char* szBuf,int nLen)
{
	int i;
	printf("\n");
	for (i = 0;i<nLen;i++)
		printf("%d ",szBuf[i]);
	printf("\n");
}