problem1_2.cpp

传教士野人渡河问题C++代码实现,更改N和K即可实现不同数目问题的求解

#include<iostream>
using namespace std;

const int N = 5;
const int K = 3;

typedef struct dbnode
{
	int ML;
	int CL;
	int BL;
	int p[20];
	int num;
	int flag;
	struct dbnode *prior,*next;
}dblinklist;

int ML(N),CL(N),BL(1),ml,cl,bl;

int P[K+1][K+1];
int A[N+1][N+1][2];

int count = 0;

bool isValid(int ML,int CL,int BL)
{
	if(ML<0||CL<0||BL<0)
		return false;

	if(ML>N||CL>N)
		return false;

	if(BL!=0&&BL!=1)
		return false;

	if((ML!=0&&ML<CL)||((N-ML)!=0&&(N-ML)<(N-CL)))
		return false;
	else
		return true;
}

void initA(int A[N+1][N+1][2])
{
	int ML,CL,BL;
	int count = 0;
	for(ML=0;ML<=N;ML++)
		for(CL=0;CL<=N;CL++)
			for(BL=0;BL<=1;BL++)
			{
				cout<<'('<<ML<<','<<CL
					<<','<<BL<<')';
				if(!isValid(ML,CL,BL))
				{
					cout<<"不合法"<<endl;
					A[ML][CL][BL] = 3;
				}
				else
				{
					A[ML][CL][BL] = 0;
					count++;
					cout<<endl;
				}
			}
	cout<<"可用状态数为"<<count<<endl;
}

void initP(int p[K+1][K+1])
{
	for(int i=0;i<=K;i++)
		for(int j=0;j<=K;j++)
		{
			if(i==0&&j==0)
			{
				p[i][j] = 0;
				continue;
			}
			if(i+j > K)
			{
				p[i][j] = 0;
				continue;
			}
			if(i!=0&&i<j)
				p[i][j] = 0;
			else
				p[i][j] = 1;
		}
}



dblinklist* findPath()
{
	dblinklist *head,*p,*s;
	//int count(0);
	bool flag = true;
	head = (dblinklist *)malloc(sizeof(dblinklist));

	p = head;
	while(flag)
	{
		if(count==0)
		{
			s = (dblinklist *)malloc(sizeof(dblinklist));
			s->ML = ML;
			s->CL = CL;
			s->BL = BL;
			s->num = 0;
			s->flag = 0;
			p->next = s;
			s->prior = p;
			p = s;
			count++;
			A[ML][CL][BL] = 1;
			A[0][0][0] = 2;
		}
		/*else
		{
			s = (dblinklist *)malloc(sizeof(dblinklist));
			s->ML = p->ML;
			s->CL = p->CL;
			s->BL = p->BL;
			s->num = 0;
			s->flag = 0;
			p->next = s;
			s->prior = p;
			p = s;
		}*/

		for(int i=0;i<=K;i++)
			for(int j=0;j<=K;j++)
			{
				if(P[i][j]==1)
				{
					ml=s->ML,cl=s->CL,bl=s->BL;
					if(bl==1)
					{
						ml-=i;
						cl-=j;
						bl=0;
					}
					else
					{
						ml+=i;
						cl+=j;
						bl=1;
					}
					if(!isValid(ml,cl,bl))
						continue;
					if(A[ml][cl][bl]==3)
						continue;
					else if(A[ml][cl][bl]==4)
						continue;//该状态已被验证无法到达结果
					else if(A[ml][cl][bl]==2)
					{
						s->p[s->num] = i*10+j;
						s->num++;;//找到可用路径,跳出
					}
					else if(A[ml][cl][bl]==1)
						continue;//绕回,继续
					else if(A[ml][cl][bl]==5)
					{
						A[ml][cl][bl] = 0;
						continue;
					}
					else
					{
						s->p[s->num] = i*10+j;
						s->num++;
						A[ml][cl][bl] = 5;
						//cout<<"可至状态:"<<'p'<<i<<j<<"\t->\t"<<'('<<ml<<'\t'<<cl<<'\t'<<bl<<')'<<endl;
						//cout<<endl;
					}
				}
			}

		if(s->num == 0)
		{
			while(count!=0)
			{
				A[s->ML][s->CL][s->BL] = 4;
				s = s->prior;
				p = s->prior;
				delete s->next;
				count--;
				if(s->num == 0)
				{
					continue;
				}
				else
				{
					p = s;
					break;
				}
			}
			if(count==0)
				return NULL;
		}

		s = (dblinklist *)malloc(sizeof(dblinklist));
		s->ML = p->ML;
		s->CL = p->CL;
		s->BL = p->BL;
		s->num = 0;
		s->flag = 0;
		p->next = s;
		s->prior = p;
		
		if(s->BL==1)
		{
			s->ML-=(p->p)[0]/10;
			s->CL-=(p->p)[0]%10;
			s->BL = 0;
		}
		else
		{
			s->ML+=(p->p)[0]/10;
			s->CL+=(p->p)[0]%10;
			s->BL = 1;
		}
		for(int k=0;k<p->num-1;k++)
			p->p[k] = p->p[k+1];
		p->num--;
		p = s;

		count++;

		if(A[s->ML][s->CL][s->BL]==2)
			flag = false;
		else
			A[s->ML][s->CL][s->BL] = 1;
	}
	head->prior = p;
	p->next = NULL;
	return head;
}

dblinklist* findPath(dblinklist *phead)
{
	dblinklist *head,*p,*s;
	head = phead;
	//int count(0);
	bool flag = true;
	//head = (dblinklist *)malloc(sizeof(dblinklist));

	s = head->prior->prior;
	delete s->next;
	count--;
	p = s;
	if(s->num == 0)
	{
		while(count!=0)
		{
			A[s->ML][s->CL][s->BL] = 2;
			s = s->prior;
			p = s->prior;
			delete s->next;
			count--;
			if(s->num == 0)
			{
				continue;
			}
			else
			{
				p = s;
				break;
			}
		}
		if(count==0)
			return NULL;
	}
	
	s = (dblinklist *)malloc(sizeof(dblinklist));
	s->ML = p->ML;
	s->CL = p->CL;
	s->BL = p->BL;
	s->num = 0;
	s->flag = 0;
	p->next = s;
	s->prior = p;
		
	if(s->BL==1)
	{
		s->ML-=(p->p)[0]/10;
		s->CL-=(p->p)[0]%10;
		s->BL = 0;
	}
	else
	{
		s->ML+=(p->p)[0]/10;
		s->CL+=(p->p)[0]%10;
		s->BL = 1;
	}
	for(int k=0;k<p->num-1;k++)
		p->p[k] = p->p[k+1];
	p->num--;
	p = s;

	count++;

	if(A[s->ML][s->CL][s->BL]==2)
		flag = false;

	while(flag)
	{
		for(int i=0;i<=K;i++)
			for(int j=0;j<=K;j++)
			{
				if(P[i][j]==1)
				{
					ml=s->ML,cl=s->CL,bl=s->BL;
					if(bl==1)
					{
						ml-=i;
						cl-=j;
						bl=0;
					}
					else
					{
						ml+=i;
						cl+=j;
						bl=1;
					}
					if(!isValid(ml,cl,bl))
						continue;
					if(A[ml][cl][bl]==3)
						continue;
					else if(A[ml][cl][bl]==4)
						continue;//该状态已被验证无法到达结果
					else if(A[ml][cl][bl]==2)
					{
						s->p[s->num] = i*10+j;
						s->num++;;//找到可用路径,跳出
					}
					else if(A[ml][cl][bl]==1)
						continue;//绕回,继续
					else if(A[ml][cl][bl]==5)
					{
						A[ml][cl][bl] = 0;
						continue;
					}
					else
					{
						s->p[s->num] = i*10+j;
						s->num++;
						A[ml][cl][bl] = 5;//此标记用于防止搜索原路返回
						//cout<<"可至状态:"<<'p'<<i<<j<<"\t->\t"<<'('<<ml<<'\t'<<cl<<'\t'<<bl<<')'<<endl;
						//cout<<endl;
					}
				}
			}

		if(s->num == 0)
		{
			while(count!=0)
			{
				A[s->ML][s->CL][s->BL] = 4;
				s = s->prior;
				p = s->prior;
				delete s->next;
				count--;
				if(s->num == 0)
				{
					continue;
				}
				else
				{
					p = s;
					break;
				}
			}
			if(count==0)
				return NULL;
		}

		s = (dblinklist *)malloc(sizeof(dblinklist));
		s->ML = p->ML;
		s->CL = p->CL;
		s->BL = p->BL;
		s->num = 0;
		s->flag = 0;
		p->next = s;
		s->prior = p;
		
		if(s->BL==1)
		{
			s->ML-=(p->p)[0]/10;
			s->CL-=(p->p)[0]%10;
			s->BL = 0;
		}
		else
		{
			s->ML+=(p->p)[0]/10;
			s->CL+=(p->p)[0]%10;
			s->BL = 1;
		}
		for(int k=0;k<p->num-1;k++)
			p->p[k] = p->p[k+1];
		p->num--;
		p = s;

		count++;

		if(A[s->ML][s->CL][s->BL]==2)
			flag = false;
		else
			A[s->ML][s->CL][s->BL] = 1;
	}
	head->prior = p;
	p->next = NULL;
	return head;
}

void show_list(dblinklist *linklist)
{
	dblinklist *alinklist;
	int i = 0;
	alinklist = linklist->next;
	while(alinklist->next!=NULL)
	{
		if(i!=0&&i%5==0)
		{
			cout<<endl;
		}
		cout<<'('<<alinklist->ML<<','<<alinklist->CL<<','<<alinklist->BL<<')'<<'\t';
		i++;
		alinklist = alinklist->next;
	}
	if(i%5==0) cout<<endl;
	cout<<'('<<alinklist->ML<<','<<alinklist->CL<<','<<alinklist->BL<<')'<<endl<<endl;
}

int main()
{
	dblinklist *linklist;
	initA(A);
	initP(P);
	linklist = findPath();
	while(linklist!=NULL)
	{
		show_list(linklist);
		linklist = findPath(linklist);
	}
	getchar();
	return 0;
}