mgwt.cpp

迷宫是一道经典的问题。本程序中通过栈来实现迷宫的求解。

#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#define FALSE 0
#define ERROR 0
#define OK 1
#define TRUE 1
#define M 15
#define N 15 
struct postype                                 //定义迷宫内点的坐标类型
{ 
	int  x1;
    int  y1;
};
struct SElemType    
{
	int x;                                     //x行
    int y;                                     //y列
    int d;                                     //d下一步的方向             
}; 
struct StackNode       
{
	SElemType  elem;
    struct StackNode  *next;
};
typedef StackNode *LinkStack;
                                               //所需函数
int InitStack(LinkStack &S)                    //构造空栈
{   
	S=NULL;
    return OK;
}
int StackEmpty(LinkStack S)                    //判断栈是否为空
{              
	if(S==NULL)
       return TRUE;
    else 
       return FALSE;
}
int Push(LinkStack &S, SElemType e)            //压入新数据元素
{              
	LinkStack p;
    p=(LinkStack)malloc(sizeof(StackNode));
    p->elem=e;
    p->next=S;
    S=p;
    return OK;
}
int Pop(LinkStack &S,SElemType &e)             //栈顶元素出栈
{             
	LinkStack p;
    if(!StackEmpty(S))
	{
		e=S->elem;
        p=S;
        S=S->next;
        free(p);
        return OK;
	}
    else
        return ERROR;
}
void MazePath(postype begin,postype end,int maze[M][N],int diradd[4][2]) 
{
	int i,j,d;int a,b;
    SElemType elem,e;
    LinkStack S1, S2;
    InitStack(S1);
    InitStack(S2);
    maze[begin.x1][begin.y1]=2;                //入口点作上标记
    elem.x=begin.x1;
    elem.y=begin.y1; 
    elem.d=-1;                                 //开始为-1
    Push(S1,elem);
    while(!StackEmpty(S1))                     //栈不为空 有路径可走
	{
		Pop(S1,elem);
        i=elem.x;
        j=elem.y;
        d=elem.d+1;                            //下一个方向
        while(d<4)     
		{                                      //开始试探东南西北各个方向
			a=i+diradd[d][0];
            b=j+diradd[d][1];

            if(a==end.x1 && b==end.y1 && maze[a][b]==0)   //如果到了出口
			{
				elem.x=i;
                elem.y=j;
                elem.d=d;
                Push(S1,elem); 
                elem.x=a;
                elem.y=b;
                elem.d=886;                    //方向输出为-1 判断是否到了出口
                Push(S1,elem);  
                printf("\n0=东 1=南 2=西 3=北\n 方向为 886为则走出迷宫\n\n");
                while(S1)                      //逆置序列 并输出迷宫路径序列
				{
					Pop(S1,e);Push(S2,e);
				}
                while(S2)
				{
				    Pop(S2,e);
                    printf("-(%d,%d,%d)-",e.x,e.y,e.d);
				}
                printf("\n(行坐标,列坐标,方向)\n");
                return ;
			}
            if(maze[a][b]==0)                  //找到可以前进的非出口的点
			{ 
				maze[a][b]=2;                  //标记走过此点
                elem.x=i;
                elem.y=j;
                elem.d=d;      
                Push(S1,elem);                 //当前位置入栈
                i=a;                           //下一点转化为当前点
                j=b;
                d=-1;
			}
            d++;
		}
	}
    printf("没有找到可以走出此迷宫路径\n"); 
}
void initmaze( int maze[M][N])
{                                              //输入的迷宫
	int i,j;
    int m,n;                                   //迷宫行，列
    printf("请输入迷宫的行数 m=");
    scanf("%d",&m);
    printf("请输入迷宫的列数 n=");
    scanf("%d",&n);
    printf("\n请输入迷宫的各行各列\n//空格隔开//\n0代表路，1代表墙\n",m,n); 
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
    scanf("%d",&maze[i][j]); 
    printf("^_^您建立的迷宫为^_^\n");
    for(i=0;i<=m+1;i++)                        //添加一圈外围封闭墙
	{  
		maze[i][0]=1;
        maze[i][n+1]=1;
	}
    for(j=0;j<=n+1;j++)
	{
		maze[0][j]=1;
        maze[m+1][j]=1;
	}   
    for(i=0;i<=m+1;i++)                        //输出迷宫
	{ 
		for(j=0;j<=n+1;j++)
        printf("%d ",maze[i][j]); 
        printf("\n");
	}
}
void main()
{   
	printf("                 *************************************\n");
	printf("                 **** 数据结构课程设计（迷宫问题）****\n");
	printf("                 ****** 专业： 计算机科学与技术 ******\n");
	printf("                 *********   班级： 06网络  **********\n");
	printf("                 *********   学生：   陈长  **********\n");
	printf("                 *********   学号：061124084 *********\n");
	printf("                 *************************************\n");
    int t;
	do{
	int maze[M][N];
    postype begin,end;                         //begin,end入口和出口的坐标 
    int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //行增量和列增量 方向依次为东西南北
    initmaze(maze);                            //建立迷宫
    printf("\no(∩_∩)o...o(∩_∩)o...\n\n");
    printf("输入入口的横坐标,纵坐标\n不大于15(逗号隔开)");   
    scanf("%d,%d",&begin.x1,&begin.y1);
    printf("\n输入出口的横坐标,纵坐标\n不大于15(用逗号隔开)");
    scanf("%d,%d",&end.x1,&end.y1);
    MazePath(begin,end,maze,add); 
    printf("是否继续？是1 / 否0\n");
    scanf("%d",&t);
	}while(t==1);
}