数据结构学习笔记（六）迷宫求解

科技 07-16 来源： 时代萌芽

迷宫求解是一个经典的程序设计问题，目的是求出从入口到出口的所有路径。通常用“穷举回溯”的方法，即从入口出发，顺着某一个方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直到所有可能的通路都探索为止。

探索路的过程中，为了保证在任何位置上都能沿路返回，显然需要一个后进先出的存储结构来保存从入口到当前位置的路径坐标，因此在迷宫求解算法中，应用“栈”的结构是自然的事。

一、栈的基本操作：

我们首先复习一下栈的基本操作：

（1）构造一个空栈。初始化成功则返回OK，否则返回ERROR。

int InitStack(SqStack *p) {
    p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
    if (p->base == NULL)  return ERROR;    //内存分配失败
    p->top = p->base;                     //栈顶与栈底相同表示一个空栈
    p->stacksize = STACK_INIT_SIZE;
    return OK;
}

（2）判断栈中是否含有效的数据

int EmptyStack(SqStack *p) {
    //若为空栈 则返回OK，否则返回ERROR
    if (p->top == p->base) return OK;
    else return ERROR;
}

（3）顺序栈进栈，将元素e压入到栈顶。

int Push(SqStack *p, StackType e) {
    //插入元素e为新的栈顶元素
    if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间
    {
        p->base = (StackType*)realloc(p->base,(p->stacksize + STACKINCREMENT) * sizeof(StackType));
        if (p->base == NULL)   return ERROR;// 储存空间分配失败
        p->top = p->base + p->stacksize;
        p->stacksize += STACKINCREMENT;
    }
    *(p->top) = e;
    (p->top)++;
    return OK;
}

（4）顺序栈出栈，将元素e弹出

int Pop(SqStack *p, StackType *e) {
    //若栈不空，则删除p的栈顶元素，用e返回其值
    if (p->top == p->base) return ERROR;
    --(p->top);
    *e = *(p->top);
    return OK;
}

二、迷宫寻路设计思路：

以下图所示，图中绿色方块为通道，蓝色方块为墙壁，所求路径必须是简单路径，即在求得路径上不能重复出现同一通道方块。

数据结构学习笔记（六）迷宫求解

6-1

1．物理存储结构：

①迷宫数据存储于一个结构体中，数据值放置于二维数组中，其中“0”代表墙值，“1”代表通路。由于迷宫被表示为二维数组，所以，在任何时刻，迷宫中的位置都可以用行(x)，列(y)坐标来描述。代码如下：

typedef struct {
    int x;    //行值
    int y;    //列值
}PosType;

② 路径存储于一个栈中，最好采用顺序栈存储，采用链栈，队列也可，各有好处，本次先讨论顺序栈存储。

③ 将路径的坐标点（x、y)，路径的方向(初始值为-1)，存放于一个结构体中。

//栈的元素类型
typedef struct
{
int id;         //通道块在路径上的序号
PosType seat;   //在迷宫中的坐标位置
    int di;          //从当前通道块走向下一位置的“方向”
} SElemType;        
//顺序栈的结构
typedef struct {
    StackType *base;   //在构造之前和销毁之后，base的值为NULL
    StackType *top;    //栈顶指针
    int stackSize;      //当前已分配的存储空间，以元素为单位
}SqStack;

2、逻辑实现思路

数据结构学习笔记（六）迷宫求解

6-2

按上图所示，目的是寻找出路，假设“当前位置”是遍历过程中某一时刻所在图中的位置，则求迷宫中一条从进口到出口路径的中心思想是：

（1）若当前位置“可通”，则纳入“当前路径”，把当前位置（x,y)及方向信息入栈，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；

（2）若当前位置“不可通”，则应顺着“来路返回”退回到“上一方块”然后朝着“来向”之外的三个方向继续探索；

（3）若该通道方块四周四个方块都“不可通”，即应从“当前路径”上删除该通道方块信息，即“出栈”。

这里要注意两点：

（1）所谓“下一位置”，指“当前位置”的四个方向（东，西，南、北）上相邻的方块。

（2）假设以栈记录“当前路径”则栈顶中存放的是“当前路径上最后一个通道方块”。由些“纳入路径”的操作就是“入栈”；从当前路径上删除前一通道的操作即为“出栈”。

所以迷宫求解出口问题算法描述以下：

Do{
若当前位置可通，
    则{
        当前位置信息（位置，方向）插入栈顶
        若该位置是出口位置，则探索结束；
        否则切换到“下一位置”（默认以东邻方向为新的位置)
       }
否则，
       若栈不空并且栈顶位置还有其他方向未探索过，
       则寻找栈顶（当前位置）的下一个位置（沿顺时针方向）
       若栈不空但栈顶位置的四个方向均一不相通
       则{ 删除栈顶位置，退回上一通道方块
       若栈不空，则重新测试当前栈顶的下一位置
       直到找到一个可通的相邻通道或出栈至栈空；
      }
}

需要说明的是，所谓的当前位置可通，指的是未曾走到过的通道块，即要求该方块位置栈记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置压入”；

“从当前路径上删除前一块通道块”的操作即为“弹出”。不仅是通道块，而且不在当前路径上(否则路径不是简单路径)，也不是曾经纳入过路径的通道块(否则只能在死胡同内转圈)。

三、迷宫寻路算法实现

走迷宫的过程跟进栈出栈一样，移动一个方位就进栈，走不动了，就原路退回，就相当于退栈，所以我们首先用一个多维数组来构建迷宫。代码如下：

void InitMaze()
{
    int i, j, x1, y1;
    printf("请输入迷宫的行数，列数(包括外墙):");
    scanf("%d%d", &x, &y);
    for (i = 1; i < x - 1; i++)
        for (j = 1; j < y - 1; j++)
            maze[i][j] = 1;  //定义通道初值为1
    printf("请输入迷宫内墙单元数:");
    scanf("%d", &j);
    printf("请依次输入迷宫内墙每个单元的行数，列数:
");

    for(i=1;i<=j;i++)
    {
        scanf("%d%d", &x1, &y1);
        maze[x1][y1] = 0; //定义墙值为0
    }
}

接着绘制迷宫并显示出来，代码描述如下：

void PrintMaze() {
    //输出迷宫结构
    int i, j;
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
            printf("%3d", maze[i][j]);
        printf("
");
    }
}

代码运行后，结构图如下：

数据结构学习笔记（六）迷宫求解

6-3

迷宫中某一个位置都可能面临2到4个方面的选择，如图所示：

数据结构学习笔记（六）迷宫求解

6-4

以当前位置坐标为（0，0），可能移动的方向数组值以下：

Direction[4] = {{0,1},{1,0},{0，-1},{-1，0}}，表示移动东南西北四个方向。那么探索方向的代码如下：

PosType NextPos(PosType seat,int di)
{
    seat.x += direction[di].x;
    seat.y += direction[di].y;
    return seat;
}

然后根据以上逻辑思维设计迷宫寻路算法，若迷宫maze中存在从入口start到出口end的通道，则求得一条路径存放在栈中，并返回TRUE；否则返回FAlSE：

Status MazePath(PosType start, PosType end)
{
    SqStack S;     // 存储探索过的通道块
    SElemType e;   // e存储当前通道块信息
    PosType curPos;   //当前位置
    InitStack(&S);     //初始化轨迹栈
    curPos = start;    // 设定当前位置为"出口位置"
    do
    {
        if (Pass(curPos)) //当前可以通过，则是未曾走到的通道块
        {
            FootPrint(curPos); //留下足迹
            e.ord = curStep;  //栈元素序号为当前序号
            e.seat = curPos;  //栈元素位置为当前位置
            e.di = 0;  //从当前位置出发，下一位置向东走
            Push(&S, e); //入栈当前位置及其状态
            curStep++;   //足迹加1
            if (curPos.x == end.x&&curPos.y == end.y)  //到达出口
                return TRUE;
            curPos = NextPos(curPos, e.di); //由当前位置及移动方向确定下一个当前位置
        }
        else  //当前位置不能通过
        if (!EmptyStack(&S))  //栈不为空
        {
            Pop(&S, &e); // 退栈到前一位置
            curStep--;  //足迹减1
            while (e.di == 3 && !EmptyStack(&S))  //前一位置处于最后一个方向(北)
            {
                MarkPrint(e.seat); //留下不能通过的标记(-1)
                Pop(&S, &e); //退一步
                curStep--; //足迹再减1
            }
            if (e.di < 3)  //没有到最后一个方向(北)
            {
                e.di++;  //换下一个方向探索
                Push(&S, e); //入栈该位置的下一个方向
                curStep++;// 足迹加1
                curPos = NextPos(e.seat, e.di);
            }
        }
    }
    while (!EmptyStack(&S));
    return FALSE;
}

源代码（C语言）参考如下：

#include 
#include 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXLENGTH 25  //设迷宫最大行列为25
#define STACK_INIT_SIZE 100//储存空间初始分配量
#define STACK_INCREMENT  10//存储空间分配增量
typedef int Status;
typedef struct {
    int x;  //行值
    int y;  //列值
}PosType;  //迷宫坐标位置类型
//栈元素类型
typedef struct
{
    int ord;      //序号
    int di;       //方向
    PosType seat; //位置
} SElemType;
//顺序栈
typedef struct {
    SElemType *base;   //在构造之前和销毁之后，base的值为NULL
    SElemType *top;    //栈顶指针
    int stackSize;     //当前已分配的存储空间，以元素为单位
}SqStack;

//迷宫数组[行][列]
typedef int MazeType[MAXLENGTH][MAXLENGTH];

//{行增量，列增量}，移动方向依次为东南西北
PosType direction[4] = { {0,1},{1,0},{0,-1},{-1,0} };

//迷宫数组
MazeType maze;

//迷宫的行，列
int x, y;

//迷宫入口坐标，出口坐标
PosType begin, end;

//当前足迹，初值在入口处为1
int curStep = 1;

//栈的初始化
int InitStack(SqStack *p) {
    p->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (p->base == NULL)  return ERROR;  //内存分配失败
    p->top = p->base;     //栈顶与栈底相同表示一个空栈
    p->stackSize = STACK_INIT_SIZE;
    return OK;
}

//判断栈是否为空
int EmptyStack(SqStack *p) {
    //若为空栈 则返回OK，否则返回ERROR
    if (p->top == p->base) return OK;
    else return ERROR;
}

//顺序栈的压入
int Push(SqStack *p, SElemType e) {
    //插入元素e为新的栈顶元素
    if ((p->top - p->base) >= p->stackSize)   //栈满，追加储存空间
    {
        p->base = (SElemType*)realloc(p->base, (p->stackSize + STACK_INCREMENT) * sizeof(SElemType));
        if (p->base == NULL)   return ERROR;// 储存空间分配失败
        p->top = p->base + p->stackSize;
        p->stackSize += STACK_INCREMENT;
    }
    *(p->top) = e;
    (p->top)++;
    return OK;
}

// 顺序栈的弹出
int Pop(SqStack *p, SElemType *e) {
    //若栈不空，则删除p的栈顶元素，用e返回其值
    if (p->top == p->base) return ERROR;
    --(p->top);
    *e = *(p->top);
    return OK;
}

//设定迷宫布局(墙值为0，通道值为1)
//全局变量maze 未初始化 所以均为值均为0
void InitMaze()
{
    int i, j, x1, y1;
    printf("请输入迷宫的行数，列数(包括外墙):");
    scanf("%d%d", &x, &y);
    for (i = 1; i < x - 1; i++)
        for (j = 1; j < y - 1; j++)
            maze[i][j] = 1;  //定义通道初值为1
    printf("请输入迷宫内墙单元数:");
    scanf("%d", &j);
    printf("请依次输入迷宫内墙每个单元的行数，列数:
");
    for(i=1;i<=j;i++)
    {
        scanf("%d%d", &x1, &y1);
        maze[x1][y1] = 0; //定义墙值为0
    }
}

//标记迷宫方块不可通过
void MarkPrint(PosType seat)
{
    maze[seat.x][seat.y] = -1;
}

//当迷宫方块点的值为1，return OK;
//否则return ERROR;
Status Pass(PosType seat)
{
    if (maze[seat.x][seat.y] == 1){
        return OK;
    }
    else{
        return ERROR;
    }
}

//使迷宫方块点的值变为足迹,表示经过
void FootPrint(PosType seat)
{
    maze[seat.x][seat.y] = curStep;
}

//根据当前位置及移动方向di，修改方块点为下一位置
PosType NextPos(PosType seat,int di)
{
    seat.x += direction[di].x;
    seat.y += direction[di].y;
    return seat;
}

//若迷宫maze中存在从入口start到出口end的通道
//则求得一条存放在栈中，并返回TRUE；否则返回FAlSE
Status MazePath(PosType start, PosType end)
{
    SqStack S;    // 存储探索过的通道块
    SElemType e;     // e存储当前通道块信息
    PosType curPos;   //当前位置
    InitStack(&S);
    curPos = start;    // 设定当前位置为"出口位置"
    do
    {
        if (Pass(curPos)) //当前可以通过，则是未曾走到的通道块
        {
            FootPrint(curPos); //留下足迹
            e.ord = curStep;  //栈元素序号为当前序号
            e.seat = curPos;  //栈元素位置为当前位置
            e.di = 0;  //从当前位置出发，默认下一位置为东
            Push(&S, e); //入栈当前位置及其状态
            curStep++;   //足迹加1
            if (curPos.x == end.x&&curPos.y == end.y)  //到达出口
                return TRUE;
            curPos = NextPos(curPos, e.di); //由当前位置及移动方向确定下一个当前位置
        }
        else //当前位置不能通过
        if (!EmptyStack(&S))  //栈不为空
        {
            Pop(&S, &e); // 退栈到前一位置
            curStep--;  //足迹减1
            while (e.di == 3 && !EmptyStack(&S))  //前一位置处于最后一个方向(北)
            {
                MarkPrint(e.seat); //留下不能通过的标记(-1)
                Pop(&S, &e); //退一步
                curStep--; //足迹再减1
            }
            if (e.di < 3)  //没有到最后一个方向(北)
            {
                e.di++;  //换下一个方向探索
                Push(&S, e); //入栈该位置的下一个方向
                curStep++;// 足迹加1
                curPos = NextPos(e.seat, e.di);
            }
        }
    }
    while (!EmptyStack(&S));
    return FALSE;
}

  //绘制迷宫结构
void PrintMaze() {
    int i, j;
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
            printf("%3d", maze[i][j]);
        printf("
");
    }
}

int main()
{
    InitMaze();  //初始化迷宫
    printf("迷宫结构如下:
");
    PrintMaze();
    printf("请输入入口的行数，列数:");
    scanf("%d%d", &begin.x, &begin.y);
    printf("请输入出口的行数，列数:");
    scanf("%d%d", &end.x, &end.y);
    printf("从此迷宫入口到出口的一条路径如下:
");
    if (MazePath(begin, end)) //有通路
    {
        PrintMaze();
    }
    else
        printf("此迷宫没有从入口到出口的路径
");
    return 0;
}
数据结构学习笔记（六）迷宫求解

数据结构学习笔记（六）迷宫求解

  • 支付宝打赏
  • 微信打赏
    • 数据结构   迷宫   学习笔记
    发表评论
    留言与评论（共有 0 条评论） “”
       
    验证码：

    相关文章

    Java8 学习笔记 - List.forEach() 和 for(item : list) 的区别
    Java8 学习笔记 - List.forEach()
    设计模式学习笔记（二）工厂模式、模板模式和策略模式的混合使用
    设计模式学习笔记（二）工厂模式、模板
    「Node学习笔记」接收处理表单数据的好方法-formidable
    「Node学习笔记」接收处理表单数据
    高分考生学习笔记被追捧成“武功秘籍”，这些笔记真是万能“钥匙”？
    高分考生学习笔记被追捧成“武功秘
    给2010年后华语犯罪片排名：《心迷宫》前三，《毒战》不是第一
    给2010年后华语犯罪片排名：《心迷宫
    真实or虚幻？深度解读《潘神的迷宫》的2个关键背景
    真实or虚幻？深度解读《潘神的迷宫》

    推荐文章

    最热点击文章

    热门标签