n传教士与n野人问题(非a算法).cpp

历史上著名的N教士与N野人问题

#include<stdio.h>
#define MAXNUM 100

//判断状态是否安全的数组
int used[MAXNUM][MAXNUM][2];

struct Status
{
	int m;
	int c;
	int b;
}s[MAXNUM];//解路径

int N,K;

void init();//初始化函数
bool search(int n);//搜索函数

int main()
{

	init();
    if( !search(1) )
		printf("NO ANSER!\n");
	return 0;
}


void init()
{
	scanf("%d%d",&N,&K);

	//找出安全状态
	for(int i = 0;i <= N;i++)
		for(int j=0;j <= N;j++)
		{
			if( (i==0 || i==N) || ( (i >= j) && (N-i) >= (N-j) ) )
				used[i][j][0] = used[i][j][1]=0;  
			else
				used[i][j][0] = used[i][j][1]=1;
		}

	//初始化解路径第一个结点
	s[0].m = s[0].c = N;
	s[0].b = 1;
	used[N][N][1]=1;
}

bool search(int n)
{
	int i = 0,j = 0,max;

	//找到解
	if( used[0][0][0] == 1 )
	{
		for(i = 0;i < (n - 1);i++)
		{
			printf("(%d,%d,%d) -> ",s[i].m,s[i].c,s[i].b);
		}
		printf("(%d,%d,%d)\n ",s[i].m,s[i].c,s[i].b);
		return true;
	}
	
	
	//船在左岸情况
	if(s[n-1].b)
	{
		//找到当前可以最大渡河人数
		if(s[n-1].m + s[n-1].c >= K)
			max=K;
		else
			max=s[n-1].m + s[n-1].c;


		//利用A*算法公式依次扩展求解
		for(i = max;i > 0;i-- )
		{
			if(s[n-1].m > i)
				j=i;
			else
				j=s[n-1].m;

			for(;j >= 0;j--)
			{
				if(i - j > s[n-1].c)
					break;
				if( (j == 0 || j >= i-j) && !used[ s[n-1].m - j ][ s[n-1].c - i + j ][0])
				{
					s[n].m = s[n-1].m - j;
					s[n].c = s[n-1].c - i + j;
					s[n].b = 0;
					used[ s[n-1].m - j ][ s[n-1].c - i + j ][0] = 1;
					if(search(n+1))
						return true;
					else
						used[ s[n-1].m - j ][ s[n-1].c - i + j ][0] = 0;
				}
			}
		}
	}
	//船在右岸的情况
	else
	{
		//找到当前可以最大渡河人数
		if(N - s[n-1].m + N - s[n-1].c >= K)
			max=K;
		else
			max=2*N - s[n-1].m - s[n-1].c;


		//利用A*算法公式依次扩展求解
		for(i = 1;i <= max;i++ )
			for(j = 0;j <= (N-s[n-1].m) && j <= i;j++)
			{
				if(i - j > N - s[n-1].c)
					continue;
					
				if( (j == 0 || j >= i-j) && !used[ s[n-1].m + j ][ s[n-1].c + i - j ][1])
				{
					s[n].m = s[n-1].m + j;
					s[n].c = s[n-1].c + i - j;
					s[n].b = 1;
					used[ s[n-1].m + j ][ s[n-1].c + i - j ][1] = 1;
					if(search(n+1))
						return true;
					else
						used[ s[n-1].m + j ][ s[n-1].c + i - j ][1] = 0;
				}
			}
	}

	//没找到解返回false
	return false;

}