拼搏

拼搏

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

admin
数据结构学习笔记（六）迷宫求解-第1张-游戏相关-拼搏

前言：

今天我们对“第1关:迷宫问题的思路”大概比较注重，咱们都需要分析一些“第1关:迷宫问题的思路”的相关文章。那么小编也在网摘上收集了一些对于“第1关:迷宫问题的思路””的相关内容，希望你们能喜欢，看官们一起来了解一下吧！

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

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

一、栈的基本操作：

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

（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("请依次输入迷宫内墙每个单元的行数，列数:\n");    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("\n");    }}

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

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 <stdio.h>#include <stdlib.h>#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;//当前足迹，初值在入口处为1int 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 未初始化 所以均为值均为0void 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("请依次输入迷宫内墙每个单元的行数，列数:\n");    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；否则返回FAlSEStatus 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("\n");    }}int main(){    InitMaze();  //初始化迷宫    printf("迷宫结构如下:\n");    PrintMaze();    printf("请输入入口的行数，列数:");    scanf("%d%d", &begin.x, &begin.y);    printf("请输入出口的行数，列数:");    scanf("%d%d", &end.x, &end.y);    printf("从此迷宫入口到出口的一条路径如下:\n");    if (MazePath(begin, end)) //有通路    {        PrintMaze();    }    else        printf("此迷宫没有从入口到出口的路径\n");    return 0;}
  • 随机文章
  • 三国志14威力加强版隐藏要素,三国志14最新补丁
  • 幸运召唤师2021年1月官方地址 lol幸运召唤师腾讯官网进入方法
  • 热血江湖2转刺客怎么加点_热血江湖刺客加点顺序
  • 超进化物语纹章有什么用 超进化物语纹章系统解析_出血纹章怎么获取
  • 机械迷城图文攻略大全详解,机械迷城攻略第九关电梯不动
  • 版本热门打野，无敌酒桶养猪的正确攻略
  • 赛尔号星球大战尤纳斯打法_赛尔号手游尤纳斯怎么打?
  • 王者荣耀礼包怎么领取？_王者荣耀英雄自选礼包怎么领取
  • 腾讯火影忍者疾风传手鞠技能介绍,火影忍者中的手鞠
  • 天龙八部怎么充值？？？,新天龙八部 充值中心
  • CF战队密码和战队密码保护问题都忘了,怎么办？_cf战队密码忘了怎么办问题擦密码问题也忘了咋办啊
  • 开心消消乐有哪关卡有四星_开心消消乐四星关去哪看

    • 标签 第1关迷宫问题的思路

    版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。

    上一篇《高达OL》官方宣布：游戏将于2022年3月30日停服

    上一篇2016年，那个被白人美女喂水喝的2岁非洲男孩，后来怎么样了？

    相关文章