[LeetCode]The Maze II

又是图的问题，找最短路径。这道题用Dijkstra就行，Dijkstra其实就是每条边带权重的BFS，和不带权重的BFS的区别就是，Dijkstra用的是priority queue，并且最短路径是在从priority queue取下节点展开的时候获得（第一次见到不一定是最短路径，还有可能继续更新），而不带权重的BFS在我们第一次见到目标节点的时候最短路径就找到了。具体算法和证明就不在这细讲，这是比较熟悉的算法了。这道题不需要事先建图，因为每一步我们可以找到相邻的节点。如果是找所有点到起点的最短路径，我们用map来记录是否展开和最短路径，如果只是找一个点，用set来记录是否展开过就行，类似BFS，代码如下：

	class Solution {
	public:
	int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
	int m = maze.size(), n = m? maze[0].size(): 0, to = destination[0] * n + destination[1], from = start[0] * n + start[1];
	if(!m || !n)return -1;
	unordered_set<int> visited;
	vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2){ return p1.first > p2.first; };
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
	pq.push({0, from});
	while(pq.size())
	{
	auto p = pq.top();
	pq.pop();
	if(visited.find(p.second) != visited.end())
	continue;
	if(to == p.second)
	return p.first;
	visited.insert(p.second);
	int i = p.second / n, j = p.second % n;
	for(auto& dir : dirs)
	{
	int x = i, y = j, dist = p.first;
	while(x >= 0 && x < m && y >= 0 && y < n && !maze[x][y])
	{
	x += dir.first;
	y += dir.second;
	++dist;
	}
	x -= dir.first;
	y -= dir.second;
	--dist;
	pq.push({dist, x * n + y});
	}
	}
	return -1;
	}
	};

view raw The Maze II.cpp hosted with ❤ by GitHub