C++图与深度优先

目录

深度规则

寻路准备

1.真实地图

2.路线记录

3.起点 终点

4.坐标结构

5.方向结构

6.辅助地图

7.判断

8.探路用石头

9.寻路

10.路线的打印

总体

带权的图为网 边的长度

深度规则

方向 - 优先级

栈结构保存 先入后出 后入先出

寻路准备

1.真实地图

//真实地图
#define MAP_ROW 10
#define MAP_COL 10

2.路线记录

3.起点 终点

//起点 终点
	MyPoint beginPoint = { 2, 2 };
	MyPoint endPoint = { 8,8 };

4.坐标结构

//坐标结构
struct MyPoint
{
	int col, row;

};

5.方向结构

//方向 —— 枚举
enum Path_Dir
{
	P_UP,
	P_LEFT,
	P_DOWN,
	P_RIGHT //逆时针
};

6.辅助地图

//辅助地图 - 草稿地图
struct PathNode
{
	int val;//路况
	Path_Dir dir;
	bool isFind; //是否已走过

};

7.判断

//下一步能不能走
bool isMove(PathNode pArr[MAP_ROW][MAP_COL], int row,int col)
{
	//算法具有健壮性
	//判断 空地 是否已经走过
	if (row < 0 || row >= MAP_ROW || col < 0 || col >= MAP_COL)
	{
		return false;
	}
	else if (pArr[row][col].val == 0 && pArr[row][col].isFind == false)
	{
		return true;
	}
	return false;
}

8.探路用石头

//探路用石头
	MyPoint NearPoint = beginPoint;

9.寻路

//寻路 不知道多少步
	while (true)
	{
		//根据方向执行
		switch (pathArr[NearPoint.row][NearPoint.col].dir)
		{
		case P_UP:
			//改变方向
			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 };
				mst.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 };
				mst.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 };
				mst.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 };
				mst.push(temp);
				NearPoint = temp;
			}
			else
			{
				//死胡同 退栈
				//这个位置要设为已走
				pathArr[NearPoint.row][NearPoint.col].isFind = true;
               //推栈
				MyPoint tempPoint = mst.top();
				cout << "退回 ：row -" << tempPoint.row << ", col -" << tempPoint.col << endl;
				mst.pop();
				//栈为空 找不到终点
				if (!mst.empty())
				{
					NearPoint = mst.top();
				}
				else{
					cout << "没有路了" << endl;
					return 0;
				}
			}
			break;
		default:
			break;
		}
		//找到终点了 
		if (NearPoint.row == endPoint.row&&NearPoint.col == endPoint.col)
		{
			break;
		}
	}

10.路线的打印

总体

#include 
#include 
using namespace std;

//真实地图
#define MAP_ROW 10
#define MAP_COL 10

//栈结构
#include

//坐标结构
struct MyPoint
{
	int col, row;

};
//方向 —— 枚举
enum Path_Dir
{
	P_UP,
	P_LEFT,
	P_DOWN,
	P_RIGHT //逆时针
};

//辅助地图 - 草稿地图
struct PathNode
{
	int val;//路况
	Path_Dir dir;
	bool isFind; //是否已走过

};

//下一步能不能走
bool isMove(PathNode pArr[MAP_ROW][MAP_COL], int row,int col)
{
	//算法具有健壮性
	//判断 空地 是否已经走过
	if (row < 0 || row >= MAP_ROW || col < 0 || col >= MAP_COL)
	{
		return false;
	}
	else if (pArr[row][col].val == 0 && pArr[row][col].isFind == false)
	{
		return true;
	}
	return false;
}

int main()
{
	//真实地图
	int mapArr[MAP_ROW][MAP_COL] = {
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
		{ 1, 0, 0, 1, 0, 1, 0, 1, 0, 1 },
		{ 1, 0, 0, 1, 0, 1, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 },
		{ 1, 0, 0, 0, 0, 1, 0, 1, 0, 1 },
		{ 1, 0, 1, 1, 0, 0, 0, 1, 0, 1 },
		{ 1, 0, 0, 1, 0, 1, 0, 1, 0, 1 },
		{ 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
	};
	//栈结构
	stack mst;

	//起点 终点
	MyPoint beginPoint = { 2, 2 };
	MyPoint endPoint = { 8,8 };
	//辅助地图
	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].isFind = false;
			pathArr[i][j].dir = P_UP;
			pathArr[i][j].val = mapArr[i][j]; //复制真实路况
		}
	}
	//起点入栈
	mst.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;
			if (isMove(pathArr, NearPoint.row - 1, NearPoint.col))
			{
				//可以走，将当前位置设置为已走
				pathArr[NearPoint.row][NearPoint.col].isFind = true;
				//入栈
				MyPoint temp = { NearPoint.row - 1, NearPoint.col };
				mst.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 };
				mst.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 };
				mst.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 };
				mst.push(temp);
				NearPoint = temp;
			}
			else
			{
				//死胡同 退栈
				//这个位置要设为已走
				pathArr[NearPoint.row][NearPoint.col].isFind = true;
               //推栈
				MyPoint tempPoint = mst.top();
				cout << "退回 ：row -" << tempPoint.row << ", col -" << tempPoint.col << endl;
				mst.pop();
				//栈为空 找不到终点
				if (!mst.empty())
				{
					NearPoint = mst.top();
				}
				else{
					cout << "没有路了" << endl;
					return 0;
				}
			}
			break;
		default:
			break;
		}
		//找到终点了 
		if (NearPoint.row == endPoint.row&&NearPoint.col == endPoint.col)
		{
			break;
		}
	}
  //打印地图
	cout << "----------------------n";
	while (!mst.empty())
	{
		MyPoint tempPoint = mst.top();
		cout << "路线 ：row -" << tempPoint.row << ", col -" << tempPoint.col << endl;
		mst.pop();
	}
	system("pause");
	return 0;
}