欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索C++

程序员文章站 2022-05-22 20:59:51
...

图论
使用栈容器
起始方向不一样会影响寻路速度和路径
有多条路径的情况下无法找到最短路径
用于知道终点的方位的场景
MyStack.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 { return pBuff[len - 1]; }
	bool empty() const { return len == 0; }
};

template<typename T>
void CMyStack<T>::pop()
{
	--len;
}

template<typename 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 != nullptr)
			delete[] pBuff;
		pBuff = tempBuff;
	}
	pBuff[len++] = elem;
}

template<typename T>
void CMyStack<T>::clear()
{
	if (pBuff != nullptr)
		delete[] pBuff;
	pBuff = nullptr;
	len = maxSize = 0;
}

template<typename T>
CMyStack<T>::~CMyStack()
{
	clear();
}

template<typename T>
CMyStack<T>::CMyStack()
{
	pBuff = nullptr;
	len = maxSize = 0;
}

#include "stdafx.h"
#include "MyStack.h"

//深度优先搜索
//规则:沿一个方向进行行走,到了岔路口又一次选择一个方向进行前进,如果碰到死胡同退回到上一个岔路口重新选择方向
//		走过的路不会再走,一次走一个节点

//1、准备地图 (二维数组,用1表示是障碍,不可通行,用0表示可以通行)
#define MAP_ROW 10
#define MAP_COL 10

//2、准备方向
enum Path_Dir{ p_up, p_down,p_left,p_right };

//3、准备一个栈,用来保存搜索过程中可以行走的路径点信息(在规划中有后进的先出)

//4、准备一个结构,用来保存每一个路径点在二维数组的行列值
struct MyPoint
{
	int row, col;
};

//5、准备一个辅助数组(1、资源地图数组不能变;2、对资源地图要进数据标记)
struct PathNode
{
	int val;//保存原始资源的路径点信息
	Path_Dir dir;//当前路径点的方向标记
	bool isFind;//当前路径点是否被访问过
};

//准备一个函数,用来判断参数的坐标是否可以通行
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 _tmain(int argc, _TCHAR* argv[])
{
	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 }
	};

	//第6步
	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;//表示给地图中的每一个节点都设定一个初始方向
		}
	}

	//第7步
	MyPoint beginPoint = { 1, 1 };
	MyPoint endPoint = { 8, 8 };

	//第8步:准备一个容器,用来保存可通行路径点
	CMyStack<MyPoint> ms;
	ms.push(beginPoint);//把起点压入到容器中,用来查找后续的结点

	//第9步:准备一个辅助坐标点,帮助来判断下一个可通行位置
	MyPoint NearPoint = beginPoint;//辅助点先为起点,然后通过起点设定的方向来对周边路径进行搜索

	//第10步:开始寻路
	while (true)//无法确定循环次数
	{
		switch (pathArr[NearPoint.row][NearPoint.col].dir)//判断当前起点在辅助数组中设定的方向
		{
		case p_up:
			//if (pathArr[NearPoint.row - 1][NearPoint.col].val == 0 &&	//表示当前点的上一行位置是可通行的
			//	pathArr[NearPoint.row - 1][NearPoint.col].isFind == false)//表示当前点的上一行位置是没有访问的
			pathArr[NearPoint.row][NearPoint.col].dir = p_left;//当前路口的下一个方向标记出来
			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;//当前路口的下一个方向标记出来
			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;//当前路口的下一个方向标记出来
			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://最后一个方向,表示前面三个方向已经搜索完成
			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();
	}
	return 0;
}