[LeetCode]The Maze III

和Maze II十分类似，区别就是变成hole了，不需要停在那，经过就可以掉进去，顺便再记录一个路径。题目要求如果有多短最短路径的的话取lexicographical order最小的一个，我们在priority queue排序的时候只要最短路径长度相同的情况下，根据记录路径的string的大小来排就行了，因为当展开的节点是target的时候，如果有其他的最短路径，肯定已经在priority queue上了，因为这些路径肯定是从某些最短路径更短的节点展开而来，而那些节点，肯定在target之前被展开。代码如下：

	class Solution {
	public:
	string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
	int m = maze.size(), n = m? maze[0].size(): 0, dest = hole[0] * n + hole[1], from = ball[0] * n + ball[1];
	unordered_set<int> visited;
	vector<pair<int, int>> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	vector<char> dirPath{'u', 'd', 'l', 'r'};
	auto comp = [](const tuple<int, string, int>& t1, tuple<int, string, int>& t2){ return get<0>(t1) == get<0>(t2)? get<1>(t1) > get<1>(t2): get<0>(t1) > get<0>(t2); };
	priority_queue<tuple<int, string, int>, vector<tuple<int, string, int>>, decltype(comp)> pq(comp);
	pq.push(make_tuple(0, "", from));
	while(pq.size())
	{
	auto t = pq.top();
	pq.pop();
	if(visited.find(get<2>(t)) != visited.end())
	continue;
	if(get<2>(t) == dest)
	return get<1>(t);
	visited.insert(get<2>(t));
	for(int k = 0; k < 4; ++k)
	{
	int x = get<2>(t) / n, y = get<2>(t) % n, dist = get<0>(t);
	auto p = dir[k];
	while(x >= 0 && x < m && y >= 0 && y < n && !maze[x][y] && (x != hole[0] || y != hole[1]))
	{
	x += p.first;
	y += p.second;
	++dist;
	}
	if(x != hole[0] || y != hole[1])
	{
	x -= p.first;
	y -= p.second;
	--dist;
	}
	pq.push(make_tuple(dist, get<1>(t) + dirPath[k], x * n + y));
	}
	}
	return "impossible";
	}
	};

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