C语言实现野人与传教士过河问题-改进版

#include <stdio.h>
#define MAX 100
//状态
struct Rec
{
	int left_c;		//左岸传教士
	int right_c;	//右岸传教士
	int left_y;		//左岸野人
	int right_y;	//右岸野人
	int boat_location;	//靠岸情况
};
struct rec_Cal
{
	int first, second;
};
struct Rec arr[MAX];
int index=0;		//下标
int numpass=0;		//成功的路径数量
int start_c,start_y, boat_member_max;//初始化
int cnt;

rec_Cal cal[MAX];

//计算当最大最船量为boat_member_max的所有乘船情况
void Cal()
{
	int st = 0;
	for(int i = 0; i <= boat_member_max; ++i)
	{
		if(i != 0)
			st = 0;
		else 
			st = 1;
		for(int j = st; j <= boat_member_max-i; ++j)
		{
			cnt++;
			cal[cnt].first = i, cal[cnt].second = j;
		}
	}
	printf("当船只最多承载%d个人的时候，合法的渡河方案\n", boat_member_max);
	printf("	----传教士人数----野人人数----\n");
	for(int i = 1; i <= cnt; ++i)
		printf("[%d] ----%5d	----%5d		----\n", i, 
			cal[i].first, cal[i].second);
//	printf("cnt = %d\n", cnt);
}

bool check(Rec t)
{
	//是否重复操作
	for(int i = 0; i < index; i++)
	{
		if((t.left_c == arr[i].left_c && t.left_y == arr[i].left_y) 
			&& (t.boat_location == arr[i].boat_location))
		{
			return false;
		}
	}
	//人数小于0 出错
	if(t.left_c < 0 || t.left_y < 0 || t.right_c < 0 || t.right_y < 0  )
	{
		return false;
	}
	
	/*
	传教士是否被吃
	1、左岸：在传教士人数 不等于0 的情况下，传教士人数 < 野人人数
	2、右岸：在传教士人数 不等于0 的情况下，传教士人数 < 野人人数
	*/
	if((t.left_c != 0 && t.left_c < t.left_y) || 
		(t.right_c < t.right_y && t.right_c != 0) )
	{
		return false;
	}
	return true;
}
int handle(Rec t)
{
	//是否达到目标状态
	if(	t.right_c == start_c && t.right_y == start_y)
	{
		numpass++;
		printf("\n找到第%d条路径！\n",numpass);
		printf("左岸传教士数\t左岸野人数\t右岸传教士数\t右岸野人数\t船值靠岸\n");
		for(int i = 0; i <= index; i++)
		{
			printf("%4d\t\t",arr[i].left_c);
			printf("%4d\t\t",arr[i].left_y);
			printf("%4d\t\t",arr[i].right_c);
			printf("%4d\t\t",arr[i].right_y);
			if(arr[i].boat_location == 1)
				printf("left");
			else 
				printf("right");
//			printf("%2d\t",arr[i].boat_location);
			printf("\n");
		}
		//找到多条路径的关键一
		return 0;
	}
	if(!check(t))  //查看是否满足条件
		return 0;
	for(int i = 1; i <= cnt; ++i)
	{
		//定义一个临时节点
		struct Rec ttt;
		ttt.left_c = t.left_c - cal[i].first * t.boat_location;
		ttt.left_y = t.left_y - cal[i].second * t.boat_location;
		ttt.right_c = t.right_c + cal[i].first * t.boat_location;
		ttt.right_y = t.right_y + cal[i].second * t.boat_location;
		ttt.boat_location = ( -1 * t.boat_location);
		arr[++index] = ttt;
		handle(arr[index]);			//递归调入点
		--index;
	}
	//找到多条路径的关键二
	return 0;
}


int main()
{
	printf("请输入初始传教士人数：");
	scanf("%d",&start_c);
	printf("请输入初始传教士人数：");
	scanf("%d",&start_y);
	printf("请输入最大船载量：");
	scanf("%d", &boat_member_max);
	arr[index].left_c = start_c;		//初始状态全部在左岸、目的状态全部在右岸
	arr[index].left_y = start_y;
	arr[index].right_c = 0;
	arr[index].right_y = 0;
	arr[index].boat_location = 1;		//初始状态船在左岸
	Cal();
	handle(arr[index]);
	printf("已为您找到%d条过河路径！并且已全部加载完毕！\n",numpass);
	return 0;
}