[栈](1.2)迷宫求解

书上这讲解可能不适合我这种低智商人吧,下边推送懒猫老师的视频

点击此处跳到视频

下面做对懒猫老师的讲解做一个学习心得

说句实话吧,没得她的讲解,我估计一晚上都摸不透,先上书上的伪码

do
{
   若当前位置可通
   则{
      将当前位置插入栈顶
      若该位置是出口位置,则结束
      否则切换当前位置的东邻方块为新的当前位置
    }
否则,
   若栈不为空,且栈顶位置尚有其他位置方向未经探索,
     则设定新的当前位置沿着方向找到栈顶位置的下一组邻块
   若栈不空但栈顶位置的四周均不可通
     则{
        删去栈顶位置
        若栈不空,则重新测试新的栈顶位置
             直到找到一个可通的相邻的块或出栈至栈空;
      }
}while(栈不空)

书上的算法我就不写了,说实话,看不懂,很恶心,下列算法由懒猫老师的伪码转换而来

void MazeStack(Maze* S, int maze[][10], Direct direct[])
{
    int x, y, di;//当前位置
    int line, col;//下一位置
    maze[1][1] = -1;
    BOX temp;
    temp.x = 1, temp.y = 1, temp.di = -1;
    Push(S, temp);
    while (S->base <= S->top)
    {
        Pop(S, &temp);
        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 = line;
                y = col;
                maze[line][col] = -1;/*记录足迹*/
                if (x == 8 && y == 8)
                {
                    printf("找到出口,路径为:");
                    return 0;
                }
                else/*不是出口则更新方向*/
                {

                    di = 0;
                }
            }
            else/*不可行换个方向*/
            {
                di++;
            }
        }
    }
}

通过上述代码做一个笔记。

思路:

  • 定义一个坐标结构,定义一个方向结构,定义一个栈

  • 初始化一个入口,从入口出发,已走过的路径压入栈顶

  • 从方向顺位向前走,

    判断下一路径是否可行

    • 如果不可行,则替换方向,继续测试
    • 如果可行,将当前路径压入栈顶,更新下一路径为当前路径
    • 判断是否为出口,如果是,则结束。

    • 如果不为出口,则继续向前走
  • 当四个方向均不可行时,将栈顶元素出栈,继续测试,直到找到有方向可行的路径结点

  • 当栈为空时,将所有可行路径测试完毕后没有出口,则返回没有出口

首先我们可以以一个二维数组来存放迷宫,由于在路径外围需要有一堵墙,所以需要一个大小为[M+2][N+2]的数组来存迷宫坐标

如以下定义

int maze[10][10] = { 
          {1,1,1,1,1,1,1,1,1,1},
      {1,0,1,1,1,1,1,1,1,1},
      {1,0,0,0,0,1,1,1,1,1},
      {1,0,1,1,1,1,1,1,1,1},
      {1,0,0,0,0,0,1,1,1,1},
      {1,1,1,1,1,0,1,1,1,1},            
      {1,0,0,0,0,0,1,1,1,1},
      {1,0,1,1,1,1,0,0,0,1},
      {1,0,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,1,1,1,1,1} };

然后我们需要定义一个坐标结构:

typedef struct
{
    int x, y;//迷宫路径坐标
    int di;//方向
}BOX;

然后我们需要定义一个方向结构

typedef struct
{
    int incX, incY;//方向增量;

}Direct;//方向
                    //右    下    左     上
Direct direct[4] = { {0,1},{1,0},{-1,0},{0,-1} };

最后我们需要定义一个栈结构(由书要求,使用动态顺序存储结构实现栈)

typedef struct Stack
{
    BOX *base;//动态顺序表表示,底指针
    BOX* top;//顶指针
}Maze;

我们需要注意的是:抽象来说,程序有两个最重要的判断点,如下图所示

img

我们可以看到,在初始化入口以后,将坐标压入了栈内,但是进入循环后又取了除了,按懒猫老师的思路来看,确实是更好的控制了循环,这个时候。

当前路径是为:1,1,0,取得是栈内弹出来的路径,进入循环后,判断的是当前路径下一路径,如果觉得很绕,可以看变量的定义

  • x,y,di,就是当前路径和方向
  • line,col就是当前路径的下一路径

我们可以看如下的代码:

img

程序通过方向赋予了line和col的值,这时候进入判断

  • 如果可行,就将当前路径压入堆栈,

    然后将下一路径更新为当前路径

    • 然后判断下一路径是否为出口,如果不是,则将方向更新为0
  • 如果不可行,则替换方向

若四个方向均不可走,就让栈中弹出上一路径的坐标,进入判断,这儿比较难以理解,我们可以这样来看:

只有当line和col可行的时候,才会将x,y,di压入堆栈,是否将当前路径压入堆栈,程序判断的是它的下一路径是否可行,只有当下一路径可行的时候,当前路径才会压入堆栈,否则四个方向都测试完后,是个死胡同,当前路径不会压入堆栈,而会将上一路径弹出来进行判断

也就是说,由于程序默认优先级最高的方向是东,也就是左边,那么如果 出现:

img墙对应数组中的1 -1对应已走的路径 0代表可走的路径

如上所示,当前位置的四个方向都不可行,那么它不会压入堆栈,栈顶的坐标是它的前一位置这时程序需要做的就是将它的前一个位置弹出来,换个方向来获取正确的方向。

也就是说,只有line和col在坐标内为0的时候,x,y,di才会压入堆栈,否则四个方向测试完后,将会弹出上一个坐标作为判断。对应代码如下所示:

核心思想就是利用栈后进先出的特性,利用二维数组存储迷宫,行列作为坐标,方向增量作为方向,来将正确的方向压入栈,若碰到死胡同,则弹出栈顶元素换个方向测试 ,直到出口或所有路径都已走完,同样,已走的路径需要用-1来替换,否则会陷入死循环内。

附:单链表实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int x, y;
    int di;
}BOX;
typedef struct
{
    int incX, incY;
}Dirct;
Dirct dir[4] = { {0,1},{1,0},{-1,0},{0,-1} };

typedef struct StackList
{
    BOX data;
    struct StackList* next;
}*LinkList,LNode;

LinkList head,node;

void Push(LinkList*, BOX);
void Pop(LinkList*, BOX*);
int MazeList(LinkList* , int[][10], Dirct[]);

int main()
{
    head = (LinkList)malloc(sizeof(LNode));
    head->next = NULL;
    int maze[10][10] = {
          {1,1,1,1,1,1,1,1,1,1},
          {1,0,1,1,1,1,1,1,1,1},
          {1,0,0,0,0,1,1,1,1,1},
          {1,0,1,1,1,1,1,1,1,1},
          {1,0,0,0,0,0,1,1,1,1},
          {1,1,1,1,1,0,1,1,1,1},
          {1,0,0,0,0,0,1,1,1,1},
          {1,0,1,1,1,1,0,0,0,1},
          {1,0,0,0,0,0,0,1,0,1},
          {1,1,1,1,1,1,1,1,1,1} };

    MazeList(&head, maze, dir);
    LinkList p;
    p = head->next;
    while (p != NULL)
    {
        printf("%d,%d,%d\n", p->data.x, p->data.y, p->data.di);
        p = p->next;
    }

    return 0;

}
void Push(LinkList L, BOX temp)
{
    LinkList tail = L;
    node = (LinkList)malloc(sizeof(LNode));
    node->data.x = temp.x;
    node->data.y = temp.y;
    node->data.di = temp.di;

    node->next = tail->next;
    tail->next = node;
}

void Pop(LinkList L, BOX* temp)
{
    LinkList p,tail;
    tail = L->next;
    temp->x = tail->data.x;
    temp->y = tail->data.y;
    temp->di = tail->data.di;
    p = tail;
    L->next = tail->next;
    free(p);
}
int MazeList(LinkList* L, int maze[][10], Dirct dir[])
{
    BOX temp;
    int x, y, di;
    int line, col;
    temp.x = 1, temp.y = 1; temp.di = -1;
    maze[1][1] = -1;
    Push(*L, temp);
    while ((*L)->next != NULL)
    {
        Pop(*L, &temp);
        x = temp.x, y = temp.y, di = temp.di + 1;
        while (di < 4)
        {
            col = y + dir[di].incY;
            line = x + dir[di].incX;
            if (maze[line][col] == 0)
            {
                temp.x = x;
                temp.y = y;
                temp.di = di;
                Push(*L, temp);
                maze[line][col] = -1;
                x = line;
                y = col;
                if (x == 8 && y == 8)
                {
                    printf("找到出口:");
                    return 0;
                }
                else
                {
                    di = 0;
                }
            }
            else
            {
                di++;
            }
        }

    }
    printf("迷宫无出口");
    return -1;
}

动态数组实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int x, y;
    int di;
}BOX;
typedef struct
{
    int incX, incY;
}Dirct;
Dirct dir[4] = { {0,1},{1,0},{-1,0},{0,-1} };
typedef struct SqStack
{
    BOX* base;
    BOX* top;
}SqStack;

SqStack S;

void Push(SqStack*, BOX temp);
void Pop(SqStack*, BOX*);
int MazeStack(SqStack*, int[][10], Dirct[]);

int main()
{
    S.base = (BOX*)malloc(100 * sizeof(BOX));
    S.top = S.base;
    int maze[10][10] = {
      {1,1,1,1,1,1,1,1,1,1},
      {1,0,1,1,1,1,1,1,1,1},
      {1,0,0,0,0,1,1,1,1,1},
      {1,0,1,1,1,1,1,1,1,1},
      {1,0,0,0,0,0,1,1,1,1},
      {1,1,1,1,1,0,1,1,1,1},
      {1,0,0,0,0,0,1,1,1,1},
      {1,0,1,1,1,1,0,0,0,1},
      {1,0,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,1,1,1,1,1} };

    MazeStack(&S, maze, dir);

    BOX* p;
    p = S.base;
    while (p < S.top)
    {
        printf("%d,%d,%d\n", p->x, p->y, p->di);
        p++;
    }
    system("pause");
    return 0;
}
void Push(SqStack* S, BOX temp)
{
    S->top->x = temp.x;
    S->top->y = temp.y;
    S->top->di = temp.di;
    S->top++;
}
void Pop(SqStack* S, BOX* temp)
{
    S->top--;
    temp->x = S->top->x;
    temp->y = S->top->y;
    temp->di = S->top->di;
}
int MazeStack(SqStack* S, int maze[][10], Dirct dir[])
{
    int x, y, di;
    int line, col;
    BOX temp;

    maze[1][1] = -1;
    temp.x = 1; temp.y = 1; temp.di = -1;
    Push(S, temp);

    while (S->base < S->top)
    {
        Pop(S, &temp);
        x = temp.x, y = temp.y, di = temp.di + 1;
        while(di<4)
        {
            line = x + dir[di].incX;
            col = y + dir[di].incY;
            if (maze[line][col] == 0)
            {
                temp.x = x;
                temp.y = y;
                temp.di = di;
                Push(S, temp);
                maze[line][col] = -1;
                x = line;
                y = col;
                if (x == 8 & y == 8)
                {
                    printf("yes:\n");
                    return 0;
                }
                else
                {
                    di = 0;
                }
            }
            else
            {
                di++;
            }
        }
    }
    printf("No");
    return 0;

}

a

本文链接:

https://nullcode.fun/20.html
1 + 8 =
快来做第一个评论的人吧~