迷宫求解.cpp

数据结构endy数据结构题解迷宫求解（带图）迷宫求解

#include"iostream.h"
#include"stdio.h"
#include"malloc.h"
#define NULL 0
#define MAX 10
typedef struct{
	int x,y;
}seat;
typedef struct node{
	seat data;
	int di;
	struct node *next;
}node;

int a[MAX][MAX]={{1,1,1,1,1,1,1,1,1,1},
				{1,0,0,1,0,0,0,1,0,1},
				{1,0,0,1,0,0,0,1,0,1},
				{1,0,0,0,0,1,1,0,0,1},
				{1,0,1,1,1,0,0,0,0,1},
				{1,0,0,0,1,0,0,0,0,1},
				{1,0,1,0,0,0,1,0,0,1},
				{1,0,1,1,1,0,1,1,0,1},
				{1,1,0,0,0,0,0,1,0,1},
				{1,1,1,1,1,1,1,1,1,1}};//迷宫图

void creat(node *&curpos)
{
	curpos=(node *)malloc(sizeof(node));
	curpos->data.x=1;
	curpos->data.y=1;
	curpos->di=1;
	return;
}
void init(node *&top)
{
	node *p;
	p=(node *)malloc(sizeof(node));
	top=p;
	top->next=NULL;
	top->di=0;
	return;
}

void insert(node *&top,node *&curpos)
{
	node *p;
	p=(node *)malloc(sizeof(node));
	top->di++;
	p->data.x=curpos->data.x;
	p->data.y=curpos->data.y;
	p->di=curpos->di;
	p->next=top->next;
	top->next=p;
	return;
}

void dele(node *&top)
{
	node *p;
	if(top->next!=NULL)
	{
		p=top->next;
		top->next=p->next;
		free(p);
		top->di--;
		return;
	}
	else cout<<"错误";
}

int pass(node *&wtop,node *&curpos)
{
	node *p;
	p=wtop;
	if(a[curpos->data.x][curpos->data.y]==0)
	{
		while(p->next!=NULL)
		{
			p=p->next;
			if(p->data.x==curpos->data.x&&p->data.y==curpos->data.y)
				return(0);
		}
		return(1);
	}
	else return(0);
}
void nextstep(node *top,node *&curpos)
{
	node *p;
	p=top->next;
	switch(p->di)
	{
		case 1:curpos->data.x=p->data.x;
			   curpos->data.y=p->data.y+1;break;
		case 2:curpos->data.x=p->data.x+1;
			   curpos->data.y=p->data.y;break;
		case 3:curpos->data.x=p->data.x;
			   curpos->data.y=p->data.y-1;break;
		case 4:curpos->data.x=p->data.x-1;
			   curpos->data.y=p->data.y;break;
	}
	curpos->di=1;
	return;
}
void chang(node *&top)
{
	int i,j,flag=1;
	node *p;
	p=top;
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<MAX;j++)
		{
			if(a[i][j]==1) printf("■");
			else{
				flag=1;	
				while(p->next!=NULL)
					{
						p=p->next;
						if(p->data.x==i&&p->data.y==j)
						{
							flag=0;
							switch(p->di)
							{
								case 1:printf("→");break;
								case 2:printf("↓");break;
								case 3:printf("←");break;
								case 4:printf("↑");break;
							}
						}
					}
					if(flag) printf("  ");
					p=top;
			}
		}
		printf("\n");
	}
	return;
}

int main()
{
	node *top,*wtop,*curpos,*p;
	init(top);
	init(wtop);
	creat(curpos);
	insert(top,curpos);
	insert(wtop,curpos);
	nextstep(top,curpos);
	do{
		if(pass(wtop,curpos))//可通过
		{
			insert(top,curpos);
			insert(wtop,curpos);
			if(curpos->data.x==MAX-2&&curpos->data.y==MAX-2) {chang(top);cout<<"\n\nOK!!\n";return(1);}
			nextstep(top,curpos);
		}
		else{
			if(top->next!=NULL)
			{
				p=top->next;
				while(p->di==4&&top->next!=NULL)
				{
					dele(top);
				}
				p=top->next;
				if(p==NULL)
				{cout<<"\n没有通路\n";chang(top);return(0);}
				if(p->di<4)
				{
					p->di++;
					nextstep(top,curpos);
				}
			}
			
		}
	}while(top->next!=NULL);
	return(0);
}