深度寻路算法（C++实现）

深度寻路算法，使用的是栈模板，通过将其走过的点的坐标压入栈中，然后遍历其所在位置的各个方向寻找可以通行的"路径",一般情况下当迷宫的范围不太大时，其又存在路径是可以遍历到路径的，但是深度寻路并不会寻找最短路径。并且当迷宫足够大时，且其可通行的点足够多时，也就是一直都有点压入栈中，这时是找不到迷宫的出口的，还会使栈的占用内存过大，导致栈溢出。
前面是个引子，下面开始真正的讲述深度深度优先搜索了先来说一下它的规则：
深度优先搜索的规则是沿着一个固定的方向进行行走，等到了一个岔路口再继续选择方向，如果碰上了死胡同再退回下一个岔路口重新选择方向。走过的路不会重新走，一次只走一个岔路口。
注意：深度优先搜索找到的路径与其寻找的方向有关，如果其寻找的方向不同，可能会找到不一样的路径。
下面展示一下简易的深度寻路的代码
这里先准备一个简易的模板栈
MyStack.h

#pragma once
template<class T>
class CMyStack
{
	T *pBuff;
	size_t len;
	size_t maxSize;
public:
	CMyStack();
	~CMyStack();
	void clear();
public:
	void push(T const& elem);
	void pop();
	bool empty() const { return len == 0; }
	T const& getTop() const { return pBuff[len - 1]; }
};
template<class T>
void CMyStack<T>::pop()
{
	len--;
}
template<class T>
void CMyStack<T>::push(T const& elem)
{
	if (len >= maxSize)
	{
		maxSize = maxSize + ((maxSize >> 1) > 1 ? (maxSize >> 1) : 1);
		T *tempBuff = new T[maxSize];
		for (size_t i = 0; i < len; ++i)
			tempBuff[i] = pBuff[i];
		if (pBuff)
			delete[] pBuff;
		pBuff = tempBuff;
	}
	pBuff[len++] = elem;
}
template<class T>
void CMyStack<T>::clear()
{
	if (pBuff)
		delete[] pBuff;
	pBuff = nullptr;
	len = maxSize = 0;
}
template<class T>
CMyStack<T>::~CMyStack()
{
	clear();
}
template<class T>
CMyStack<T>::CMyStack()
{
	pBuff = nullptr;
	len = maxSize = 0;
}

然后在main.cpp进行深度寻路算法

//1、需要一张地图 （二维数组来表示地图）
//在二维数组中用一个固定的数值表示可通行（一般为0）,其它的非0数值都理解不可通行
#define MAP_ROW 10
#define MAP_COL 10

//2、准备方向 帮助进行辅助寻路
enum Path_Dir {p_up,p_left,p_down,p_right};

//3、准备一个结构，用来保存每一个路径点的行列值
struct MyPoint
{
	int row, col;
};

//4、准备一个数据结构来保存寻路最终所找到的所有岔路口的坐标（准备一个栈来做为数据结构）

//5、为地图准备一个辅助的寻路地图（这个辅助地图不仅仅是一个变量能解决的，需要一个结构）
struct PathNode
{
	int val;//保存资源地图的岔路口信息
	Path_Dir dir;//为当前岔路口准备一个最初的寻路方向
	bool isFind;//当前岔路口是否被访问
};

//准备一个函数，用来判断当前坐标表示的位置是否可以通行
bool isCheckMove(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].isFind == true || p[row][col].val != 0)//判断当前行列表示的坐标已经访问过，或者当前坐标上的值为表示障碍
		return false;
	return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int mapArr[MAP_ROW][MAP_COL] = {
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 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, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 1, 0, 0, 1, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 0, 0, 1 },
		{ 0, 0, 1, 1, 1, 0, 0, 1, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 }
	};

	PathNode pathArr[MAP_ROW][MAP_COL];
	for (int i = 0; i < MAP_ROW; ++i)
	{
		for (int j = 0; j < MAP_COL; ++j)
		{
			pathArr[i][j].val = mapArr[i][j];//把资源数组的岔路口的值赋值到辅助数组中
			pathArr[i][j].isFind = false;//地图中的每一个岔路口都没有被访问过
			pathArr[i][j].dir = p_up;//为每一个岔路口初始一个初始寻路方向
		}
	}

	//第6步：准备起点和终点
	MyPoint beginPoint = { 1, 1 };
	MyPoint endPoint = { 9, 8 };

	//第7步：准备一个栈容器来保存所有的路径点
	CMyStack<MyPoint> ms;
	ms.push(beginPoint);//把起点压入容器

	//第8步：准备一个辅助的坐标变量。1、用来表示当前正在寻路的坐标值
	MyPoint currPoint = beginPoint;//最开始的辅助点就是起点，通过起点找第二个点，这个辅助点才会变成第二点的坐标

	//第9步：开始寻路
	while (true)//无法确定循环次数
	{
		switch (pathArr[currPoint.row][currPoint.col].dir)//判断一个初始方向
		{
		case p_up:
			pathArr[currPoint.row][currPoint.col].dir = p_left;//当前点的上方向不可通行，改当前点的下一次搜索方向
			if (isCheckMove(pathArr, currPoint.row - 1, currPoint.col))
			{
				//如果进入条件，表示该坐标是可通行的
				pathArr[currPoint.row][currPoint.col].isFind = true;//当前点改为已访问
				MyPoint tempPoint = { currPoint.row - 1, currPoint.col };
				ms.push(tempPoint);//把当前点的上方向可通行坐标压入容器
				currPoint = tempPoint;//把当前点的上方向可通行坐标赋值给当前坐标，以便于下一次从新的当前坐标开始查找
			}
			break;
		case p_left:
			pathArr[currPoint.row][currPoint.col].dir = p_down;//当前点的左方向不可通行，改当前点的下一次搜索方向
			if (isCheckMove(pathArr, currPoint.row, currPoint.col - 1))
			{
				//如果进入条件，表示该坐标是可通行的
				pathArr[currPoint.row][currPoint.col].isFind = true;//当前点改为已访问
				MyPoint tempPoint = { currPoint.row, currPoint.col - 1 };
				ms.push(tempPoint);//把当前点的左方向可通行坐标压入容器
				currPoint = tempPoint;//把当前点的左方向可通行坐标赋值给当前坐标，以便于下一次从新的当前坐标开始查找
			}
			break;
		case p_down:
			pathArr[currPoint.row][currPoint.col].dir = p_right;//当前点的下方向不可通行，改当前点的下一次搜索方向
			if (isCheckMove(pathArr, currPoint.row + 1, currPoint.col))
			{
				//如果进入条件，表示该坐标是可通行的
				pathArr[currPoint.row][currPoint.col].isFind = true;//当前点改为已访问
				MyPoint tempPoint = { currPoint.row + 1, currPoint.col };
				ms.push(tempPoint);//把当前点的下方向可通行坐标压入容器
				currPoint = tempPoint;//把当前点的下方向可通行坐标赋值给当前坐标，以便于下一次从新的当前坐标开始查找
			}
			break;
		case p_right:
			//注意：最后一个方向了，不需要再记录下一个方向，因为4方向搜索完成
			if (isCheckMove(pathArr, currPoint.row, currPoint.col + 1))
			{
				//如果进入条件，表示该坐标是可通行的
				pathArr[currPoint.row][currPoint.col].isFind = true;//当前点改为已访问
				MyPoint tempPoint = { currPoint.row, currPoint.col + 1 };
				ms.push(tempPoint);//把当前点的右方向可通行坐标压入容器
				currPoint = tempPoint;//把当前点的右方向可通行坐标赋值给当前坐标，以便于下一次从新的当前坐标开始查找
			}
			else
			{
				//证明当前点的4方向已经都不可通行，是死胡同
				//入栈的坐标是没有标记已经被访问的
				//MyPoint tempPoint = ms.getTop();
				pathArr[currPoint.row][currPoint.col].isFind = true;//在退栈之前，当前这个搜索的坐标标记为已经访问

				ms.pop();//当前点退栈，把当前这个表示死胡同的坐标退掉
				if (!ms.empty())//判断如果栈不为空
					currPoint = ms.getTop();//得到新的栈点元素
			}
			break;
		}
		//找到出口，没有出口 结束循环
		if (ms.empty())//没有路径，结束循环
			break;
		if (currPoint.row == endPoint.row && currPoint.col == endPoint.col)//当前点就是终点
			break;
	}

	//寻路终止，打印路径
	while (!ms.empty())
	{
		MyPoint tempPoint = ms.getTop();
		//printf("row = %d\t col = %d\n",tempPoint.row,tempPoint.col);
		pathArr[tempPoint.row][tempPoint.col].val = 5;
		ms.pop();
	}

	for (int i = 0; i < MAP_ROW; ++i)
	{
		for (int j = 0; j < MAP_COL; ++j)
		{
			switch (pathArr[i][j].val)
			{
			case 5:
				printf("* ");
				break;
			default:
				printf("^ ");
			}
		}
		printf("\n");
	}
	system("pause");
	return 0;
}