maze.cpp

本课题主要根据功能需要开发软件解决迷宫求解的问题。可以输入一个任 意大小的迷宫数据

/************************************************************ 
  作者:     胡娟  200608204105. 
  工具:     VC++ 6.0. 
  题目:     迷宫求解. 
                 "1"代表墙,"0"代表可以行走
  从入口到出口找到一条路径. 
/**********************************************************/ 

#include "stdlib.h"
#include "stdio.h"
#include "iostream.h"

#define NULL 0
#define TRUE 1
#define FALSE 0
#define NUMBER 20

typedef int Status;

typedef struct
{              //坐标，迷宫中x行y列的位置
	int x;
	int y;
}PosType;

typedef struct        
{
	int order;		//当前位置在路径上的序号 
	int directory;   //往下一坐标的方向
	PosType seat;    //当前的坐标位置
}ElementType;        //栈的元素类型

typedef struct node1   //栈类型
{
 ElementType node;
 struct node1 *next;
}StackNode,* LinkStack;  //结点类型，指针类型

void InitStack(LinkStack &head);         //初始化，设置栈空
int IsStackEmpty(LinkStack head);        //判断栈是否为空
int Push(LinkStack head, ElementType element);  //元素进栈 
int Pop(LinkStack head, ElementType &element);   //元素出栈
int GetTop(LinkStack head, ElementType &element); //取栈顶元素
int StackLength(LinkStack head);           //栈长
Status ClearStack(LinkStack &S);            //清空栈
Status DestroyStack(LinkStack &head);       //销毁栈
Status Pass(PosType curpos,int (*a)[10]);//判断当前位置是否可通过
PosType NextPos(PosType curpos,int directory);//相对于当前位置的下一方向位置坐标
void MarkPrint(int &a);//留下不能通过的标记
void PrintStack(LinkStack head);//输出栈中元素坐标


void InitStack(LinkStack &head)
{
	 head=(LinkStack)malloc(sizeof(StackNode));
	 if(head==NULL)
	 {
		 cout<<"分配存储空间失败！"<<endl;exit(0);
	 }
     head->next = NULL;
}

int IsStackEmpty(LinkStack head)
{
    if(head->next == NULL) 
		return TRUE;
    return FALSE;
}

int Push(LinkStack head, ElementType element)
{
    StackNode *newp;
    newp = (StackNode *)malloc(sizeof(StackNode));
    if(newp == NULL) 
	{
		cout<<"分配存储空间失败！"<<endl;exit(0);
	}
    newp->node = element;
    newp->next = head->next;
    head->next = newp;
    return TRUE;
}

int Pop(LinkStack head, ElementType &element)
{
    if(IsStackEmpty(head))
		return FALSE;
    StackNode *newp = head->next;
    element = newp->node;
    head->next = newp->next;
    free(newp);
    return TRUE;
}

int GetTop(LinkStack head, ElementType &element)
{
    element = head->next->node;
	if(head->next==NULL)
		return FALSE;
	return TRUE;
}

int StackLength(LinkStack head)
{
	 LinkStack p;
   	 int i=0;
	 p=head->next;
	 while(p)
	 {
		 i++;
		 p=p->next;
	 }
	 return i;
}

Status ClearStack(LinkStack &S)
{
	LinkStack p;
	while(S->next)
	{
	    p=S->next;
		S->next=S->next->next;
		delete p;
	}
	return TRUE;
}

Status DestroyStack(LinkStack &head)
{
	LinkStack q;
	while(head)
	{
		q=head->next;
	    delete head;
	    head=q;
	}
    return TRUE;
}

Status Pass(PosType curpos,int (*a)[10]) //判断当前位置是否可通过
{
	if(a[curpos.x][curpos.y]==1||a[curpos.x][curpos.y]==-1)
	return FALSE;
	return TRUE;
}

//相对于当前位置的下一方向位置坐标
PosType NextPos(PosType curpos,int directory)
{
	 switch(directory)
	{
		case 1:
			curpos.x=curpos.x+1;break;   //向东
		case 2:
		    curpos.y=curpos.y+1;break;   //向南
		case 3:
			curpos.x=curpos.x-1;break;   //向西
		case 4:
			curpos.y=curpos.y-1;break;   //向北
	}
	return curpos;

}

void MarkPrint(int &a)   //留下不能通过的标记
{
	 a=-1;
}

void PrintStack(LinkStack head)//输出栈中元素坐标
{
	LinkStack p;
	cout<<"\n\n从迷宫的出口到入口的路径为："<<endl;
	while(head->next)     //如果栈不为空，输出栈中所有元素的坐标
	{
		cout<<"("<<head->next->node.seat.x<<","<<head->next->node.seat.y<<")"<<"   ";
		p=head->next;
		head->next=head->next->next;
		free(p);
	}
}

 

Status MazePath(int (*maze)[10],PosType start,PosType end)
{								//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中
   	 LinkStack S;
	 ElementType e;
	 PosType curpos=start; //设定“当前位置”为“入口位置”
	 int curstep=1; //探索第一步
	 InitStack(S);
	 do{
		 if(Pass(curpos,maze))
		 {									//当前位置可以通过，即是未曾走到过的通道块
			e.order=curstep;
			e.directory=1;
			e.seat=curpos;        
			Push(S,e);           //加入路径
			maze[e.seat.x][e.seat.y]=-1;
			if(curpos.x==end.x&&curpos.y==end.y)//到达终点（出口）
			{
				PrintStack(S);
				return TRUE;
			}
			curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
			curstep++;//探索下一步
		 }//if
		 else
		 {      //当前位置不能通过
			if(!IsStackEmpty(S))
			 {
				Pop(S,e);
				while(e.directory==4&&!IsStackEmpty(S)) 
				{
					//maze[e.seat.x][e.seat.y]
					MarkPrint(maze[e.seat.x][e.seat.y]); //留下不能通过的痕迹，并退回一步
					Pop(S,e);
					curstep--;
				}//while
				if(e.directory<4)
				{
					 e.directory++;    //换下一方向进行探索
					 Push(S,e);   
				     maze[e.seat.x][e.seat.y]=-1;
					 curpos=NextPos(e.seat,e.directory);  //设定当前位置是该方向上的相邻块
				 }//if
			}//if
		 }//else
	}while(!IsStackEmpty(S));
    return FALSE;
}

void main()
{
 int maze[10][10]={
 //0 1 2 3 4 5 6 7 8 9
  {1,1,1,1,1,1,1,1,1,1},//0
  {1,0,0,1,1,1,1,1,1,1},//1
  {1,1,0,0,1,0,1,1,0,1},//2
  {1,1,1,0,1,0,0,1,0,1},//3
  {1,0,0,0,1,1,0,1,1,1},//4
  {1,0,0,0,1,0,0,0,1,1},//5
  {1,0,1,0,0,0,1,1,1,1},//6
  {1,0,1,1,1,0,1,1,1,1},//7
  {1,0,0,1,1,0,0,0,0,1},//8
  {1,1,1,1,1,1,1,1,1,1} //9
 };
 cout<<"\n***************迷**宫**求**解**********************************\n"<<endl;
 cout<<"迷宫测试数据如下：左上角(1,1)为入口，右下角(8,8)为出口。"<<endl;
 for (int i=1;i<9;i++)
 {
	 printf("\n        ");
	 for (int j=1;j<9;j++)
	 {
		 printf("%-4d",maze[i][j]);
	 }
 }
 PosType start,end;
 start.x=1;start.y=1;
 end.x=8;end.y=8;
 if(MazePath(maze,start,end)==1)
  cout<<"\n求解成功！"<<endl;
 else cout<<"\n求解失败！"<<endl;
}