数据结构学习第十九课(寻路算法之广度寻路)

广度寻路

#include<stdio.h>
#include<vector>
using namespace std;

#define ROW 12
#define COL 12
//方向
enum dirc { p_up, p_down, p_left, p_right };
//描述一个点
struct Point
{
	int row;
	int col;
};
//辅助地图结点类型
struct pathNode
{
	bool isFind;//是否走过
};
//准备一颗四叉树
struct treeNode
{
	Point pos;//数据
	treeNode* pParent;//指向父节点的指针
	vector<treeNode*> child;//保存孩子节点指针
};
//创建一个新结点并返回新结点地址
treeNode* createNode(int row, int col);
//判断一个点是否能走
bool canWalk(Point pos, int map[ROW][COL], bool isFind[ROW][COL]);
int main()
{
	//1 描述地图
	int map[ROW][COL] =
	{
		{1,1,1,1,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1,1,1},
		{1,0,0,0,0,0,0,0,0,0,0,1},
		{1,0,1,1,1,1,1,1,1,1,0,1},
		{1,0,1,1,1,1,1,1,1,1,0,1},
		{1,0,1,0,0,0,0,0,0,0,0,1},
		{1,0,1,0,1,1,1,1,1,1,1,1},
		{1,0,1,0,1,1,1,1,1,1,1,1},
		{1,0,1,0,1,1,1,1,1,1,1,1},
		{1,0,1,0,1,1,1,1,1,1,1,1},
		{1,0,0,0,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1,1,1}
	};

	//2 起点 终点
	Point begPos = { 1,1 };
	Point endPos = { 10,10 };
	//3 辅助地图
	bool isFind[ROW][COL] = { 0 };//表示没有走过
	//4 起点走过
	isFind[begPos.row][begPos.col] = true;
	//5 准备一颗树
	treeNode* pRoot=NULL;//根结点
	treeNode* pNew = NULL;//新结点
	//6 起点成为树的根结点
	pRoot = createNode(begPos.row, begPos.col);
	//7 寻路
	Point curPos = begPos;
	Point serPos;
	vector<treeNode*> buff;//当前层
	vector<treeNode*> temp;//临时数组
	bool isFindEnd = false;
	buff.push_back(pRoot);//当前层有且只有一个 就是起点 就是树的根结点
	while (1)
	{
		temp.clear();
		//7.1 循环遍历当前层
		for (int i = 0; i < buff.size(); i++)
		{
			curPos = buff[i]->pos;
			//7.1.1 循环找当前点周围哪些能走
			for (int j = 0; j < 4; j++)
			{
				serPos = curPos;
				switch (j)
				{
				case p_up: 
					serPos.row--;
					break;
				case p_down:
					serPos.row++;
					break;
				case p_left:
					serPos.col--;
					break;
				case p_right:
					serPos.col++;
					break;
				}
				//7.1.2 能走,就标记走过,入树,存储到数组中
				if (canWalk(serPos, map, isFind))
				{
					//1 标记走过
					isFind[serPos.row][serPos.col] = true;
					//2 入树
					//2.1
					//创建新结点
					pNew = createNode(serPos.row, serPos.col);
					// 2.2 新结点成为当前点的孩子
					buff[i]->child.push_back(buff[i]);
					// 2.3 当前点成为新结点的父
					pNew->pParent = buff[i];
					//3 存储到数组中
					temp.push_back(pNew);
					// 2找到了终点,循环结束
					if (serPos.row == endPos.row &&
						serPos.col == endPos.col)
					{
						isFindEnd = true;
						break;
					}
				}
			}
			if (isFindEnd)
			{
				break;
			}
		}
		//7.2 替换成下一层
		if (isFindEnd)
		{
			break;
		}
		buff = temp;
		//7.2.1 当前层元素个数为0,循环结束 或 找到了终点,循环结束
		// 1当前层元素个数为0,循环结束
		if (buff.size() < 1)
		{
			break;
		}
	}
	if (isFindEnd)
	{
		printf("找到了:\n");
		while (pNew)
		{
			printf("%d,%d ", pNew->pos.row, pNew->pos.col);
			pNew = pNew->pParent;
		}
		printf("\n");
	}
	return 0;
}
//创建一个新结点并返回新结点地址
treeNode* createNode(int row, int col)
{
	treeNode* pNew = new treeNode;
	memset(pNew, 0, sizeof(treeNode));//清空置零
	pNew->pos.row = row;
	pNew->pos.col = col;
	return pNew;
}

bool canWalk(Point pos, int map[ROW][COL], bool isFind[ROW][COL])
{
	//越界
	if (pos.row >= ROW || pos.row < 0 ||
		pos.col < 0 || pos.col >= COL)
	{
		return false;
	}
	//是障碍
	if (map[pos.row][pos.col])
	{
		return false;
	}
	//走过
	if (isFind[pos.row][pos.col])
	{
		return false;
	}
	return true;
}
/*
结果显示:
找到了:
10,10 10,9 10,8 10,7 10,6 10,5 10,4 10,3 10,2 10,1 9,1 8,1 7,1 6,1 5,1 4,1 3,1 2,1 1,1
*/