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

广度优先搜索求最短路径及其具体路径

程序员文章站 2022-06-11 21:07:27
...

问题:在二维矩阵中,给定起始点和终止点,求从起始点到终止点的最短路径。其中矩阵值为1代表可以通过,0代表障碍。

代码如下:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using std::vector;
struct point
{
	int x;
	int y;
	int step;
	point(int _x, int _y, int _step) :x(_x), y(_y), step(_step) {}
	point(int _x, int _y) :x(_x), y(_y), step(0){}
	point(){}
	bool operator==(const point& other)const
	{
		return x == other.x&&y == other.y;
	}
};
int minSteps_BFS(const vector<vector<int>>& path, vector<vector<point>>& mp, point src, point des, int step);
int main()
{
	vector<vector<int>> path = { { 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 0, 0, 1, 1 }, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };
	vector<vector<point>> mp(5, vector<point>(5));
	point src(0,0);
	point des(3,3);
	int step = 0;
	cout << minSteps_BFS(path, mp, src, des, step) << endl;
	cout << "具体路径如下:" << endl;
	//vector<point> res;
	while (!(mp[des.x][des.y] == src))
	{
		cout << des.x << " " << des.y << endl;
		des = mp[des.x][des.y];
	}
	cout << des.x << " " << des.y << endl;
	return 0;
}

int minSteps_BFS(const vector<vector<int>>& path, vector<vector<point>>& mp, point src, point des, int step)
{
	const int n = path.size();
	const int m = path[0].size();
	const int dx[4] = { 0, 0, -1, 1 };
	const int dy[4] = { 1, -1, 0, 0 };
	vector<vector<bool>> flag(n, vector<bool>(m, false));
	flag[src.x][src.y] = true;
	queue<point> que;
	que.push(src);
	while (!que.empty())
	{
		point p = que.front();
		for (int i = 0; i < 4; ++i)
		{
			if (p.x + dx[i] < 0 || p.x + dx[i] >= n || p.y + dy[i] < 0 || p.y + dy[i] >= m)
				continue;
			if (path[p.x + dx[i]][p.y + dy[i]] == 1 && !flag[p.x + dx[i]][p.y + dy[i]])
			{
				flag[p.x + dx[i]][p.y + dy[i]] = true;
				que.push(point(p.x + dx[i], p.y + dy[i], p.step + 1));
				mp[p.x + dx[i]][p.y + dy[i]]= p;
				if (point(p.x + dx[i], p.y + dy[i], p.step + 1) == des)
				{
					return p.step + 1;
				}
			}
		}
		que.pop();
	}
	return -1;
}

结果图:

广度优先搜索求最短路径及其具体路径