深度优先搜索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;
}
上一篇: 当然是你亲生的