数据结构:队列的应用实现
程序员文章站
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();
}
}
最终效果图:
上一篇: Datawhale二手车
下一篇: 数据结构与算法:链表及其应用