数据结构与算法——深度寻路算法

文章目录

1、介绍

2、地图的描绘

3、试探方向

4、死胡同问题

5、Stack代码

.h文件

.c文件

6、算法代码

.h文件

.c文件

1、介绍

深度寻路算法：使用的是栈模板，通过将其走过的点的坐标压入栈中，然后遍历其所在位置的各个方向寻找可以通行的"路径",一般情况下当迷宫的范围不太大时，其又存在路径是可以遍历到路径的，但是深度寻路并不会寻找最短路径。 并且 当迷宫足够大时，且其可通行的点足够多时，也就是一直都有点压入栈中，这时是找不到迷宫的出口的，还会使栈的占用内存过大，导致栈溢出。 深度优先搜索的规则是沿着一个固定的方向进行行走，等到了一个岔路口再继续选择方向，如果碰上了死胡同再退回下一个岔路口重新选择方向。 走过的路不会重新走，一次只走一个岔路口。深度寻路只能走直线 不能走斜线

2、地图的描绘

用二维数组来描述,可以用其他数据结构来描述 图结构

//地图  1表示障碍 0表示路

int map[ROWS][COLS] = {

 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

 { 1, 0, 1, 1, 0, 0, 0, 1, 1, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 0, 0, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};

3、试探方向

试探 一般是顺时针或者逆时针

好马不吃回头草

人为规定试探方向顺序并且一开始所有的点都是一样

例如：一开始每个点都是 上

试探顺序是 上 左 下 右 逆时针

已经走过的应当标记，试探的时候走过的不走

所以我在这里准备了预测点和辅助地图，预测点的作用是探测是墙还是路，能不能走；辅助地图的作用是标记已经走过的地方和方向

//点

Mypoint begPos = { 1,1 };

Mypoint endPos = { 8,8 };

//辅助地图,标记起点走过

pathMap PathMap[ROWS][COLS] = { 0 };

PathMap[begPos.row][begPos.row].isFind = true;

//栈 起点入栈

Stack stack;

init(&stack);

push(&stack, &begPos);

//标记没有找到终点

bool isFindEnd = false;

//当前点

Mypoint currentPos;

currentPos.row = begPos.row;

currentPos.col = begPos.col;

//预测点

Mypoint searchPos;

4、死胡同问题

回退机制

栈结构：先入后出，后入先出

1 走过就入栈

2 遇到死胡同(每个方向都试过还不能走 最后一个方向右都不能走)回退

2.1 pop 出栈一个

2.2 跳到当前栈顶元素处

例如下图，当走到8,1的时候遇到死胡同，这里只需要把栈顶元素删掉，然后跳到当前栈顶元素

5、Stack代码

.h文件

#ifndef _MY_STACK_H_

#define _MY_STACK_H_

#include"Mytypes.h"

#include<string.h>

#include<stdlib.h>

typedef struct Stack  

{

Mypoint* pArr;     //记录内存首地址

int size;          //记录当前元素个数

int capacity;      //记录当前容量

}Stack;

//初始化

void init(Stack* S);

//添加元素

void push(Stack* S, Mypoint* pos);

//删除元素

void pop(Stack* S);

//获取栈顶元素

Mypoint* getTop(Stack* S);

//判断栈是否为空

bool isEmpty(Stack* S);

#endif // !_MY_STACK_H_

.c文件

#include "MyStack.h"

#include<assert.h>

void init(Stack* S)

{

   S->size = S->capacity = 0;

   S->pArr = NULL;

}

void push(Stack* S, Mypoint* pos)

{

   if ( S->size >= S->capacity )

   {

       S->capacity += (((S->capacity >> 1) > 1) ? (S->capacity >> 1) : 1);

       Mypoint* king = malloc(sizeof(Mypoint) * (S->capacity));

       assert(king);

       if ( S->pArr )

       {

           memcpy(king, S->pArr, sizeof(Mypoint) * (S->size));

           free(S->pArr);

       }

       S->pArr = king;

   }

   S->pArr[S->size].row = pos->row;

   S->pArr[S->size].col = pos->col;

   S->size++;

}

void pop(Stack* S)

{

   S->size--;

}

Mypoint* getTop(Stack* S)

{

   return (S->pArr + (S->size - 1));

}

bool isEmpty(Stack* S)

{

   return (S->size == 0);

}

6、算法代码

.h文件

#ifndef _MY_TYPES_H_

#define _MY_TYPES_H_

#include<stdio.h>

#include<stdbool.h>

#define ROWS 10

#define COLS 10

//地图区分

enum type { road, wall };

//方向类型，上左下右

enum direct { p_up, p_left, p_down, p_right };

//定义点类型

typedef struct Mypoint

{

int row, col;

}Mypoint;

//辅助地图类

typedef struct pathMap  

{

int dir;   //记录当前方向

bool isFind;  //是否走过 false没走过 true走过

}pathMap;

#endif

.c文件

#include"Mytypes.h"

#include"MyStack.h"

#include<windows.h>

void drawMap(int map[ROWS][COLS],Mypoint* p)  

{

Sleep(300);

system("cls");

for (int i = 0; i < ROWS; i++)  

{

 for (int j = 0; j < COLS; j++)  

 {

  if (p->row == i && p->col == j)  

  {

   printf("人");

  }

  else if (wall == map[i][j])  

  {

   printf("墙");

  }

  else  

  {

   printf("  ");

  }

 }

 printf("\n");

}

}

int main()

{

//地图  1表示障碍 0表示路

int map[ROWS][COLS] = {

 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

 { 1, 0, 1, 1, 0, 0, 0, 1, 1, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 0, 0, 0, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 1 },

 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};

//点

Mypoint begPos = { 1,1 };

Mypoint endPos = { 8,8 };

//辅助地图,标记起点走过

pathMap PathMap[ROWS][COLS] = { 0 };

PathMap[begPos.row][begPos.row].isFind = true;

//栈 起点入栈

Stack stack;

init(&stack);

push(&stack, &begPos);

//标记没有找到终点

bool isFindEnd = false;

//当前点

Mypoint currentPos;

currentPos.row = begPos.row;

currentPos.col = begPos.col;

//预测点

Mypoint searchPos;

//寻路

while (1)

{

 //找到试探点

 searchPos.row = currentPos.row;

 searchPos.col = currentPos.col;

 //根据当前点的试探方向，确定试探点

 switch (PathMap[currentPos.row][currentPos.col].dir)

 {

  case p_up:

   searchPos.row--;

   //试探方向改变

   PathMap[currentPos.row][currentPos.col].dir = p_left;

   //判断能不能走

   if ( road == map[searchPos.row][searchPos.col] &&

    PathMap[searchPos.row][searchPos.col].isFind == false )

   {

    //走

    currentPos.row = searchPos.row;

    currentPos.col = searchPos.col;

    //记录走过

    PathMap[currentPos.row][currentPos.col].isFind = true;

    //入栈

    push(&stack, &currentPos);

   }

   break;

  case p_left:

   searchPos.col--;

   //试探方向改变

   PathMap[currentPos.row][currentPos.col].dir = p_down;

   //判断能不能走

   if (road == map[searchPos.row][searchPos.col] &&

    PathMap[searchPos.row][searchPos.col].isFind == false)

   {

    //走

    currentPos.row = searchPos.row;

    currentPos.col = searchPos.col;

    //记录走过

    PathMap[currentPos.row][currentPos.col].isFind = true;

    //入栈

    push(&stack, &currentPos);

   }

   break;

  case p_down:

   searchPos.row++;

   //试探方向改变

   PathMap[currentPos.row][currentPos.col].dir = p_right;

   //判断能不能走

   if (road == map[searchPos.row][searchPos.col] &&

    PathMap[searchPos.row][searchPos.col].isFind == false)

   {

    //走

    currentPos.row = searchPos.row;

    currentPos.col = searchPos.col;

    //记录走过

    PathMap[currentPos.row][currentPos.col].isFind = true;

    //入栈

    push(&stack, &currentPos);

   }

   break;

  case p_right:

   searchPos.col++;

   //判断能不能走

   if (road == map[searchPos.row][searchPos.col] &&

    PathMap[searchPos.row][searchPos.col].isFind == false)

   {

    //走

    currentPos.row = searchPos.row;

    currentPos.col = searchPos.col;

    //记录走过

    PathMap[currentPos.row][currentPos.col].isFind = true;

    //入栈

    push(&stack, &currentPos);

   }

   else

   {

    //出栈

    pop(&stack);

    //跳到当前栈顶元素处

    currentPos.row = getTop(&stack)->row;

    currentPos.col = getTop(&stack)->col;

   }

   break;

 }

 drawMap(map, &currentPos);

 //是否找到终点了

 if ( currentPos.col == endPos.col && currentPos.row == endPos.col )

 {

  isFindEnd = true;

  break;

 }

 //退回去了 栈空

 if (isEmpty(&stack)) break;

}

if ( isFindEnd )

{

 printf("找到终点了：\n");

 while ( !isEmpty(&stack ))

 {

  printf("(%d,%d)", getTop(&stack)->row, getTop(&stack)->col);

  pop(&stack);

 }

 printf("\n");

}

return 0;

}

版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_72157449/article/details/129766874