1.cpp

此程序是求迷宫中从入口 到出口的所有路径。在搜索中还要建立一个堆栈

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define First_SIZE 100 //存储空间初始分配量
#define INCREMENT 10  //存储空间分配增量
typedef struct  
{       //迷宫中r行c列的位置
	int r;
    int c;
}PostType;
typedef struct
{
	int ord;      //当前位置在路径上的序号
	PostType seat;//当前坐标
	int di;       //往下一坐标的方向
}SElemType;        //栈元素类型
typedef struct
{
	SElemType* base; 
	SElemType* top;
	int stackSize;   
}Stack;              
Status InitStack(Stack &S)
{	//构造空栈s
	S.base=(SElemType*)malloc(First_SIZE *sizeof(SElemType));
	if(!S.base)
		exit(OVERFLOW); 
	S.top=S.base;
	S.stackSize=First_SIZE;
	return OK;
} 
Status StackEmpty(Stack S)
{//若s为空返回TRUE,否则返回FALSE
	if(S.top==S.base)
		return TRUE;
	return FALSE;
} 
Status Push(Stack &S,SElemType e)
{//插入元素e为新的栈顶元素
	if( (S.top-S.base) >=S.stackSize) 
	{
		S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit(OVERFLOW);    
		S.top=S.base+S.stackSize;
		S.stackSize+=INCREMENT;
	}
	*S.top++=e;
	return OK;
}
Status Pop(Stack &S,SElemType &e)
{//若栈不空删除栈顶元素用e返回并返回OK，否则返回ERROR
	if(S.top==S.base)
		return ERROR;
	e=*--S.top;
      return OK;
} 
Status DestroyStack(Stack &S)
{//销毁栈S
	free(S.base);
	S.top=S.base;
	return OK;
}

#define max 20//迷宫包括外墙最大行列数目
typedef struct
{
	int r;
	int c;
	char adr[max][max]; 
}MazeType;   
Status InitMaze(MazeType &maze)
{//初始化迷宫若成功返回TRUE,否则返回FALSE
	int m,n,i,j;
	printf("请输入迷宫的行和列：\n ");
	scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
	for(i=0;i<=maze.c+1;i++) 
	{ 
		maze.adr[0][i]='#';
		maze.adr[maze.r+1][i]='#';
	} 
	for(i=0;i<=maze.r+1;i++) 
	{ 
		maze.adr[i][0]='#';
		maze.adr[i][maze.c+1]='#';
	}
	for(i=1;i<=maze.r;i++)
		for(j=1;j<=maze.c;j++)
			maze.adr[i][j]=' '; 
	printf("输入迷宫障碍坐标（以(-1 -1)坐标结束）： ");
	scanf("%d%d",&m,&n);//接收障碍的坐标
	while(m!=-1)
	{
		if(m>maze.r || n>maze.c) 
			exit(ERROR);
		maze.adr[m][n]='#';//迷宫障碍用'#'标记
		printf("输入迷宫障碍坐标（以(-1 -1)坐标结束）： ");
		scanf("%d%d",&m,&n);
	} 
	return OK;
} 

Status Pass(MazeType maze,PostType curpos)
{//当前位置可通则返回TURE,否则返回FALSE
	if(maze.adr[curpos.r][curpos.c]==' ')//可通
		return TRUE;
	else
		return FALSE;
} 
Status FootPrint(MazeType &maze,PostType curpos)
{//若走过并且可通返回TRUE,否则返回FALSE
    maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
	return OK;
} 
PostType NextPos(PostType &curpos,int i)
{
	PostType cpos;
	cpos=curpos;
	switch(i){        //1.2.3.4分别表示东,南,西,北方向
		case 1 : cpos.c+=1; break;
		case 2 : cpos.r+=1; break;
		case 3 : cpos.c-=1; break;
		case 4 : cpos.r-=1; break;
		default: exit(ERROR);	
	}
	return cpos;
} 
Status MarkPrint(MazeType &maze,PostType curpos)
{//曾走过但不是通路标记并返回OK
	maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
	return OK;
} 
Status MazePath(MazeType &maze,PostType start,PostType end)
{//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
	Stack S;
	PostType curpos;
	int curstep; 
	SElemType e;
	InitStack(S);
	curpos=start; 
	curstep=1;    
	do{
		if(Pass(maze,curpos))
		{//当前位置可以通过,即是未曾走到过的通道
			FootPrint(maze,curpos);//留下足迹
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);              //加入路径
			if(curpos.r==end.r&& curpos.c==end.c)
				if(!DestroyStack(S)) 
					exit(OVERFLOW); 
				else 
					return TRUE;  
			else{
				curpos=NextPos(curpos,1); //下一位置是当前位置的东邻
				curstep++;       //探索下一步
			} 
		} 
		else{    
			if(!StackEmpty(S))
			{
				Pop(S,e);
				    while(e.di==4&& !StackEmpty(S))
					{
						MarkPrint(maze,e.seat);
					    Pop(S,e); //留下不能通过的标记,并退一步
					} 
				if(e.di < 4)
				{
					e.di++;//换下一个方向探索
					Push(S,e);            
					curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻
				} 
			} 
		}
	}
		while(!StackEmpty(S));
	if(!DestroyStack(S)) 
	   exit(OVERFLOW);	    
 else 
	   return FALSE;
} 

void PrintMaze(MazeType &maze)
{//将标记路径信息的迷宫输出到终端(包括外墙)
	int i,j;
	for(i=0;i<=maze.r+1;i++) 
		printf("%4d",i);
	printf("\n\n");
	for(i=0;i<=maze.r+1;i++){
		printf("%2d",i); 
		for(j=0;j<=maze.c+1;j++)
	printf("%4c",maze.adr[i][j]);//输出迷宫当前位置的标记
		printf("\n\n");
	}
} 
 
void main(){      
	MazeType maze;
	PostType start,end;
	char cmd;
	do{
		if(!InitMaze(maze))
		{   
		    printf("迷宫创建失败!!\n");
			exit(OVERFLOW);     
		}
		do{                  
			printf("\n输入进入迷宫的坐标:");
			scanf("%d%d",&start.r,&start.c);
			if(start.r>maze.r || start.c>maze.c){
				printf("\n超出迷宫范围!\n");
				continue;
			}
		}while(start.r>maze.r || start.c>maze.c);
		do{                 //输入迷宫出口坐标
			printf("\n输入走出迷宫的坐标:");
			scanf("%d%d",&end.r,&end.c);
			if(end.r>maze.r || end.c>maze.c){
				printf("\n超出迷宫范围!\n");
				continue;
}
		}while(end.r>maze.r || end.c>maze.c);
		if(!MazePath(maze,start,end))//迷宫求解
			printf("\n不存在的路径!\n");
		else
			PrintMaze(maze);//打印路径
		printf("\n是否要继续?(按Y继续,退出按其他键!): ");
		scanf("%s",&cmd);
	}while(cmd=='y' || cmd=='Y');
	printf("\n\n05级计算机科学与技术  杨霜雪\n");
}