数据结构与算法_深度优先寻路

1. 深度优先搜索

深度优先搜索的实现步骤为，在一个已知的地图内，逐点搜索下一个路径点的四个方向是否可以同行，如果找到一个可以通行的方向，那么向前前进，如果搜索到的最前面一个点无法向前搜索，则退后，重新搜索之前搜索过点的其它方向。

2. 代码实现

.h 文件

#pragma once
template<typename T>
class CMyStack
{
 T *pBuff;
 size_t len;
 size_t maxSize;
public:
 CMyStack();
 ~CMyStack();
 void clear();
public:
 void push(T const& elem);//将元素压入容器底部
 void pop();//将元素从底部退出
 T const& getTop()const;//得到容器内倒数第二个元素
 bool empty()const;//判断容器是否为空
};
template<typename T>
inline CMyStack<T>::CMyStack()
{
 pBuff = nullptr;
 len = maxSize = 0;
}
template<typename T>
inline CMyStack<T>::~CMyStack()
{
 clear();
}
template<typename T>
inline void CMyStack<T>::clear()
{
 if (pBuff != nullptr) delete[] pBuff;
 pBuff = nullptr;
 len = maxSize=0;
}
template<typename T>
inline void CMyStack<T>::push(T const & elem)
{
 //执行从尾部压入数据的过程，添加新数据需要重新分配内存，并且创建一个临时变量
 if (len >= maxSize)
 {
  maxSize = maxSize + (((maxSize) >> 1) > 1 ? (maxSize >> 1) : 1);
  T *tempBuff = new T[maxSize];//给指针new一个内容，格式是 new 类型 [数据个数]
  for (size_t i = 0; i < len; ++i) tempBuff[i] = pBuff[i];
  if (pBuff != nullptr) delete[] pBuff;
  pBuff = tempBuff;
 }
 pBuff[len++] = elem;
}
template<typename T>
inline void CMyStack<T>::pop()
{
 --len;
}
template<typename T>
inline T const & CMyStack<T>::getTop() const
{
 // TODO: 在此处插入 return 语句
 return pBuff[len - 1];
}
template<typename T>
inline bool CMyStack<T>::empty() const
{
 return len==0;
}

. cpp 文件

#include<stdio.h>
#include"MyStack.h"
using namespace std;
#define MAP_ROW 10
#define MAP_COL 10
//准备一个方向
enum Path_Dir{p_up,p_down,p_left,p_right};
//准备一个用来保存每一个路径点在二维数组的行列值的结构
struct MyPoint
{
 int row, col;
};
//准备一个辅助数组，用来对走过的地图进行标记
struct PathNode
{
 int val;//保存原始资源的路径点信息
 Path_Dir dir;//当前路径点的方向信息
 bool isFind;//当前路径点是否被访问过
};
//准备一个地图
int mapArr[MAP_ROW][MAP_COL] =
{
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 0, 0, 1, 1, 0, 0, 0, 1, 1,
 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
 1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
bool IsMove(PathNode p[][MAP_COL],int row,int col)
{
 if (row < 0 || row >= MAP_ROW || col < 0 || col >= MAP_COL)return false;
 if (p[row][col].val != 0 || p[row][col].isFind == true)return false;
 return true;
}
int main()
{
 //将当前点位信息保存进临时数组里，防止原始数组被修改
 PathNode pathArr[MAP_ROW][MAP_COL];//表示有一个PathNode类型的二维数组，这个二维数组里包含的信息是PathNode所包含的内容
 for (int i = 0; i < MAP_ROW; ++i)
 {
  for (int j = 0; j < MAP_COL; ++j)
  {
   pathArr[i][j].dir = p_up;//表示给地图中的每个点的初始方向都设置成从上开始
   pathArr[i][j].isFind = false;//表示地图中的每个点都没有被访问过
   pathArr[i][j].val = mapArr[i][j];//将原始地图赋值给pathnode
  }
 }
 //以上内容完成了pathArr数组的赋值操作，将原始地图创建完成副本，设置初始方向为上，设置起始值均没有被访问过
 //设置人为起始方向及中点方向
 MyPoint beginPoint = { 1,1 };
 MyPoint endPoint = { 8,8 };
 //准备一个容器用来保存可以通行的路径点信息
 CMyStack<MyPoint> ms;//类名为CMyStack，对象名为 ms 模板类型为MyPoint
 ms.push(beginPoint);//将起点压入到容器中
 //准备辅助坐标点，判断下一个可以通行的位置
 MyPoint NearPoint = beginPoint;
 //开始寻路
 while (true)
 {
  switch (pathArr[NearPoint.row][NearPoint.col].dir)
  {
  case p_up:
   //自动向下一个方向移动
   pathArr[NearPoint.row][NearPoint.col].dir = p_left;
   //判断是否可以向上通过，可以通过则1、2、3
   if (IsMove(pathArr, NearPoint.row - 1, NearPoint.col))
   {
    //表示当前坐标下，方向 上 可以通行
    pathArr[NearPoint.row][NearPoint.col].isFind = true;//当前坐标改为已访问
    MyPoint temp = { NearPoint.row - 1,NearPoint.col };
    ms.push(temp);//将这个可行的坐标压入到容器中保存
    NearPoint = temp;//把这个方向上的可通行点赋值给辅助点，进行下一次搜素
   }
   break;
  case p_left:
   //自动向下一个方向移动
   pathArr[NearPoint.row][NearPoint.col].dir = p_down;
   //判断是否可以向上通过，可以通过则1、2、3
   if (IsMove(pathArr, NearPoint.row, NearPoint.col-1))
   {
    //表示当前坐标下，方向 上 可以通行
    pathArr[NearPoint.row][NearPoint.col].isFind = true;//当前坐标改为已访问
    MyPoint temp = { NearPoint.row ,NearPoint.col-1 };
    ms.push(temp);//将这个可行的坐标压入到容器中保存
    NearPoint = temp;//把这个方向上的可通行点赋值给辅助点，进行下一次搜素
   }
   break;
  case p_down:
   //自动向下一个方向移动
   pathArr[NearPoint.row][NearPoint.col].dir = p_right;
   //判断是否可以向上通过，可以通过则1、2、3
   if (IsMove(pathArr, NearPoint.row+1, NearPoint.col))
   {
    //表示当前坐标下，方向 上 可以通行
    pathArr[NearPoint.row][NearPoint.col].isFind = true;//当前坐标改为已访问
    MyPoint temp = { NearPoint.row+1 ,NearPoint.col };
    ms.push(temp);//将这个可行的坐标压入到容器中保存
    NearPoint = temp;//把这个方向上的可通行点赋值给辅助点，进行下一次搜素
   }
   break;
   //最后一个方向，前面三个方向已经搜索完成
  case p_right:
   //判断是否可以向上通过，可以通过则1、2、3
   if (IsMove(pathArr, NearPoint.row, NearPoint.col + 1))
   {
    //表示当前坐标下，方向 上 可以通行
    pathArr[NearPoint.row][NearPoint.col].isFind = true;//当前坐标改为已访问
    MyPoint temp = { NearPoint.row ,NearPoint.col + 1 };
    ms.push(temp);//将这个可行的坐标压入到容器中保存
    NearPoint = temp;//把这个方向上的可通行点赋值给辅助点，进行下一次搜素
   }
   else
   {
    //如果所有路口都不能通行则退栈
    MyPoint tempPoint = ms.getTop();//得到退栈之前的栈顶元素
    pathArr[tempPoint.row][tempPoint.col].isFind = true;
    ms.pop();
    if (!ms.empty()) NearPoint = ms.getTop();
   }
   break;
  }
  if (NearPoint.row == endPoint.row && NearPoint.col == endPoint.col) break;
  if (ms.empty()) break;
 }
 while (!ms.empty())
 {
  MyPoint tempPoint = ms.getTop();
  printf("row=%d,col=%d\n", tempPoint.row, tempPoint.col);
  ms.pop();
 }
 getchar();
 return 0;
}