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

数据结构:队列的应用实现

程序员文章站 2024-01-24 17:17:22
...

题目:

用队列求解迷宫问题的最短路径

思路:

0为迷宫通路,1无法通达
准备:先建立point存储路径点,然后建立队列,并实现入队,出队等基本操作,建立与迷宫等大的数组visited,step分别存储该点已经经过使用和到达该点时的最短步数。
实现:从起点开始,将起点放入队列,起点step[0][0]记为0,接着将该点附近不越界且可以抵达的点也放进队列,并将点处在的step记为1,visited设为1,再将队首的点四周不越界且可以抵达的点也放进队列,并将点处在的step记为2,visited设为1,如此循环直到终点,如果终点step不为0,即有最短路径可达,终点的step值即为最短路径步数。
显示路径:利用深度搜索,从终点开始,找寻四周比它小1的点,并放进栈,直到起点,最后将栈的值依次放进队列即可。

代码块:

#include "pch.h"
#include <iostream>
#include<vector>
#include<stack>
using namespace std;
struct point//存放路径点
{
	int x;
	int y;
};
struct queue
{
	point data;
	queue *next;
};
struct queptr//队列
{
	queue*front;
	queue*rear;
};
void init(queptr&q)//初始化队列
{
	q.front = new queue;
	q.rear = q.front;
	q.front->next = NULL;
}
void enqueue(queptr&q, point data)//入队操作
{
	queue *tmp = new queue;
	tmp->data = data;
	tmp->next = NULL;
	q.rear->next = tmp;
	q.rear = tmp;
}
void pop(queptr &q)//出队操作
{
	if (q.front == q.rear) {
		cout << "队空\n"; return;
	}
	queue*tmp = q.front->next;
	q.front->next = tmp->next;
	if (tmp == q.rear)q.rear = q.front;
	delete tmp;
}
point top(queptr&q)//返回队首
{
	if (q.front != q.rear) return q.front->next->data;
	else cout << "队空\n";
}
void dfs(stack<point>&s, int x, int y,int cnt, vector<vector<int>> &step)//深度搜索,从终点利用步数图搜索到起点,得到路径
{
	if (x >= 0 && x < step.size() && y >= 0 && y < step[x].size())
	{
			if (step[x][y] + 1 == cnt)
			{
				point tmp;
				tmp.x = x;
				tmp.y = y;
				s.push(tmp);
				dfs(s, x - 1, y, step[x][y], step);
				dfs(s, x + 1, y, step[x][y], step);
				dfs(s, x, y - 1, step[x][y], step);
				dfs(s, x, y + 1, step[x][y], step);
			}
	}
}
int main()
{
	vector<vector<int>>map = {//迷宫路径,0为通路,1为不通
		{0,1,0,0,0},
		{0,1,0,1,0},
		{0,0,0,0,0},
		{0,1,1,1,0},
		{0,0,0,1,0},
	};
	vector<vector<int>> step;//记录最短路径步数
	for (int i = 0; i < map.size(); i++)//初始化路径步数图
	{
		step.push_back(vector<int>(map[i].size(), 1000));
	}
	step[0][0] = 0;//起点步数为0
	queptr q;
	init(q);//建立并初始化队列
	point tmp;
	tmp.x = 0;
	tmp.y = 0;
	enqueue(q,tmp);
	map[0][0] = -1;//起点入列并将迷宫路径修改为-1,防止循环往复
	while (q.front->next!=NULL)
	{
		if (q.front->next->data.x - 1 >=0&& q.front->next->data.x - 1 <map.size()&& map[q.front->next->data.x - 1][q.front->next->data.y] == 0)
		{//搜索该点四周的点是否通路
			point next;
			next.x = q.front->next->data.x-1;
			next.y = q.front->next->data.y;//记录下一节点
			step[next.x][next.y] = step[q.front->next->data.x][q.front->next->data.y] + 1;//相应点步数增加
			map[next.x][next.y] = -1;//防止循环
			enqueue(q, next);//将目前通路点入列
		}
		if ( q.front->next->data.x + 1 >= 0 && q.front->next->data.x + 1 < map.size()&&map[q.front->next->data.x + 1][q.front->next->data.y] == 0 )
		{
			point next;
			next.x = q.front->next->data.x + 1;
			next.y = q.front->next->data.y;
			step[next.x][next.y] = step[q.front->next->data.x][q.front->next->data.y] + 1;
			map[next.x][next.y] = -1;
			enqueue(q, next);
		}
		if (q.front->next->data.y+1>=0&&q.front->next->data.y-1<map[q.front->next->data.x].size()&&map[q.front->next->data.x ][q.front->next->data.y-1] == 0)
		{
			point next;
			next.x = q.front->next->data.x;
			next.y = q.front->next->data.y-1;
			step[next.x][next.y] = step[q.front->next->data.x][q.front->next->data.y] + 1;
			map[next.x][next.y] = -1;
			enqueue(q, next);
		}
		if (q.front->next->data.y+1 >= 0 && q.front->next->data.y + 1 < map[q.front->next->data.x].size()&&map[q.front->next->data.x][q.front->next->data.y+1] == 0  )
		{
			point next;
			next.x = q.front->next->data.x;
			next.y = q.front->next->data.y+1;
			step[next.x][next.y] = step[q.front->next->data.x][q.front->next->data.y] + 1;
			map[next.x][next.y] = -1;
			enqueue(q, next);
		}
		//cout << top(q).x<<'\t'<<top(q).y<<endl;
		if (top(q).x == map.size()-1 && top(q).y == map[map.size()-1].size()-1)break;//找到最后一个结点,退出循环
		pop(q);
	}
	while (q.front!=q.rear)//清空队列
	{
		pop(q);
	}
	cout <<"迷宫的最短路径长度为:"<< step[step.size() - 1][step[step.size() - 1].size() - 1]<<endl;//最短路径长
	stack<point> s;//利用栈和步数矩阵还原路径
	if(step[step.size() - 1][step[step.size() - 1].size() - 1]-1== step[step.size() - 2][step[step.size() - 1].size() - 1])//从终点开始搜寻路径
		dfs(s, step.size() - 2, step[step.size() - 1].size() - 1, step[step.size() - 1][step[step.size() - 1].size() - 1], step);//先搜索终点上一行同一列的路径,看是否可以找到起点
	if (s.top().x!=0|| s.top().y!=0)
	{//如果上一行同一列无法到达起点,则清空栈,搜索同一行前一列是否能到达起点
		while (!s.empty())
		{
			s.pop();
		}
		if (step[step.size() - 1][step[step.size() - 1].size() - 1] - 1 == step[step.size() - 1][step[step.size() - 1].size() - 2])
			 dfs(s, step.size() - 1, step[step.size() - 1].size() - 2, step[step.size() - 1][step[step.size() - 1].size() - 1], step);//搜索
		else {
			cout << "不存在最短路径\n"; return -1;
		}
		if (s.top().x != 0 || s.top().y != 0) {
			cout << "不存在最短路径\n"; return -1;
		}
	}
	cout << "起点" << endl;
	while (!s.empty())
	{//栈从终点将路径返回添加到队列
		cout <<"->("<< s.top().x << ',' << s.top().y <<")"<< endl;
		enqueue(q, s.top());
		s.pop();
	}
}

最终效果图:
数据结构:队列的应用实现
数据结构:队列的应用实现

相关标签: c++