迷宫问题——栈实现（C语言）（数据结构与算法）

前言

本文用栈解决迷宫问题，采用C语言实现，包括问题介绍、算法简介、求解过程、代码实现、结果展示。并附有完整代码。

本文完整代码：
https://pan.baidu.com/s/1r24R6mTlGHxUkEezWm4BjQ

提取码：2bbE

一、迷宫问题

概括来说，迷宫问题就是在一个封闭空间里，事先不知道这个封闭空间的内部结构，经过个方向试探，从而找到一个出口。假设有个机器人放置在这个封闭空间的入口处：

迷宫用一个二维数组表示，0表示可以通行，1表示不可以通行
构成迷宫为类似二维数组

（可以看到这个数组周围全是1，这里1表示不同，相当于迷宫的四周，这样可以保证机器人不会在搜寻过程中不会离开迷宫，当给定的迷宫没有边界时，建议自己添加上）
在任意给定时刻，机器人只能在上下左右四个方向上移动1步
机器人只能移动到没有障碍物的位置即0的位置，且不可以离开迷宫
机器人不可以重复走某点
机器人应该搜索从起始位置到目标位置的路径，直到找到一个或者耗尽他所有可能性

二、问题分析

1.位置表示

由于迷宫构成是一个二维数组，我们可以采用坐标的形式 $(x, y)$ 来表示机器人的位置，为了方便代码实现，我将入口出的位置规定为（1，1）标蓝的位置为（1，1）如下图所示：
在这里插入图片描述

2.方向探寻

规定机器人探寻的方向为四个

dierct	incX	incY
0	0	1
1	1	0
2	0	-1
3	-1	0

我们用incX、incY分别表示x、y方向上的增量表示如果机器人往这个方向上移动其位置坐标将会发生如上的变化。可以看到上面这个方向是遵循右下左上的原则，我们就可以定义一个结构体数组分别保存incX、incY这两个变量，对其实例化后即可实现方向的增量表示。

//定义一个结构体表示方向的增量
typedef struct{
//x,y方向的增量
int incX,incY;
}Direction;

实例化：

    Direction direct[4]= {{0,1},{1,0},{0,-1},{-1,0}};

3、算法实现过程

双层循环控制，内层循环控制机器人方向探寻过程，依次探寻四个方向，外层循环保证机器人进行回溯时退栈不为空。

机器人从入口处（1，1）出发，开始按照右下左上的方向顺序进行搜索，判断四个方向上是否有路可走，这里实现过程可以利用一层循环实现，依次遍历方向搜寻的四个方向，有路可走的含义就是机器人目前所处的位置上下左右四个方向是不是有为0的取值，有的话就证明机器人目前所处的位置不是死路，是能够前进的。
因此把目前的位置和前进的方向这三个变量进行入栈操作。
入栈完成后进行位置更新。要不这个已经走过的位置用-1替换，不再用0或者1表示。

if(maze[line][col]==0)
            {
                temp.x=x;
                temp.y=y;
                temp.di=di;
                push(&S,temp.x ,temp.y ,temp.di);
                x =line;
                y =col;
                maze[line][col]= -1;

当然，如果四个方向都搜寻完，一位置这一层循环跳出了，那这样就是回溯算法的核心思想，这是机器人目前所处的位置是不会入栈的，反而会执行退栈操作，返回到前一个位置，我们之前保存的其前进的位置就有用了，用di这个方向变量同时接受收当时保存的位置，位置更新后再次进入方向搜索的循环，这样不需要重复搜索原来已经搜索过的地方，因为原来搜索过的地方是走不通的，如果入栈时不保存原来的位置就会陷入死循环。

    while(!IsEmptyStack(&S))
    {
        pop(&S,&(temp.x),&(temp.y),&(temp.di));
        x = temp.x;
        y = temp.y;
        di = temp.di +1;
        while(di <4)
        {
            line = x+ direct[di].incX;
            col = y + direct[di].incY;
            if(maze[line][col]==0)
            {
                temp.x=x;
                temp.y=y;
                temp.di=di;
                push(&S,temp.x ,temp.y ,temp.di);
                x =line;
                y =col;
                maze[line][col]= -1;
                if(x ==M && y == N)
                    {
                        //由于栈先入后出的特性这里重新定义一个栈目的就是能够正序输出其坐标
                        while(!IsEmptyStack(&S))
                        {

                            pop(&S,&(temp.x),&(temp.y),&(temp.di));
                            push(&H,temp.x ,temp.y ,temp.di);
                        }
                        while(!IsEmptyStack(&H))
                        {
                          pop(&H,&(temp.x),&(temp.y),&(temp.di));
                          printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
                        }

                        return 1;
                       // int e1,e2,e3;
                        //GetTop(&S, &e1,&e2,&e3 );
                       // printf("%d",e1);

                    }
                else di =0;
            }
            else
                di ++;
        }
    }

既然有退栈的操作，我们还要有一层循环，去判断栈是否为空，如果栈为空还没有到终点，表示这个迷宫无解，我们也要对这个结果做出反馈。
机器人搜索道路的终点应该是，机器人当前的位置坐标为最后的出口位置，即表示成功走出迷宫。
成功走出迷宫后，要对其路程进行输出，由于栈先进后出的特点，栈顶保存的位置坐标是机器人最后的走的位置，这里我采用的方法是重新定义一个栈，原有栈的结果依次出栈入新栈，打印的时候让新栈依次出栈

 while(!IsEmptyStack(&S))
                        {

                            pop(&S,&(temp.x),&(temp.y),&(temp.di));
                            push(&H,temp.x ,temp.y ,temp.di);
                        }
                        while(!IsEmptyStack(&H))
                        {
                          pop(&H,&(temp.x),&(temp.y),&(temp.di));
                          printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
                        }

二、遇到的问题与解决方案

1.结构体数组入栈的问题

栈中需要保存位置坐标x、y以及从目前该位置移动至下一个位置的方向，保存这个方向的目的就在于走错路进行退栈。无需要四个方向重新遍历，在原有基础上查找为走过的方向即可。栈中保存的不再是一个数而应该是三个数，栈顶指针top更新时不可以简单的top++，理解也很简单这三个数分配的空间定义的一个结构体抽象数据类型用到的空间，具体是多少我们很难估计，基于此考虑利用双链表实现我们在定义保存当前位置坐标与方向这个结构体时定义同样类型的指针，分别指向他的前一个节点与后一个节点，这样在更新栈顶指针所指位置时，直接将next指针传给top就能顺利完成出栈与入栈。而对于出栈一样的操作，数据出栈后，只需要把parent指针的内容传给top。由此我们可以看出，栈的实现本质上变成了双向链表的操作。分别对应其入栈出栈。简单的画了一下栈内各结点的连接过程：
当我们考虑好结构体入栈出栈的具体实现方式，就要改变原来初始化的问题。进行栈的初始化，我采用的是提前动态申请部分空间，除了空间的申请更要构建好节点之间的关系，即能够正确找到next节点与parent节点。为了能够正确描述节点之间的关系选择采用循环申请的动态空间的方式。为了保证数据能够顺利入栈，栈顶指针需要指向下一个放入数据的空间，因此让栈顶指针等于栈底指针，初始化完成，得到一个空栈。

Status InitStack(SeqStack* stack)
{
	//开辟空间
	stack->base=stack->top = (EleType*)malloc( sizeof(Box));
	int i =0;
	for(i=0; i <50;i++)
    {
      stack->top->next = (EleType*)malloc( sizeof(Box));
      stack->top->next->present = stack->top;
      stack->top = stack->top->next;
    }
	stack ->top = stack ->base;
	if (!stack->base)
	{
		exit(0);
	}
	stack->stackSize = STACK_INIT_SIZE;
	return OK;
}

二、结果展示

在这里插入图片描述