AC C++ 6ms A* search


  • 0
    struct node
    {
    	int x, y;
    	int g; // dist from start
    	int h; // dist to end
    	string path;
    	int f;
    	node() = default;
    	node(int xx, int yy, int gg, int hh, string pp = "")
    		: x(xx), y(yy), g(gg), h(hh), path(pp) {
    		f = g + h;
    	}
    };
    // hash used in unordered_set
    namespace std
    {
    	template<>
    	struct hash<pair<int, int>>
    	{
    		size_t operator()(const pair<int, int> &p) const
    		{
    			auto h1 = hash<int>{}(p.first);
    			auto h2 = hash<int>{}(p.second);
    			return	h1 ^ (h2 << 1);
    		}
    	};
    }
    class Solution
    {
    private:
    	// calculate dist
    	int dist(const pair<int, int> &lhs, const pair<int, int> &rhs)
    	{
    		return abs(lhs.first - rhs.first) + abs(lhs.second - rhs.second);
    	}
    	pair<int, int> s, e;
    	vector<pair<int, int>> dirs = { { 1, 0 },{ 0, -1 },{ 0, 1 },{ -1, 0 } };
    	vector<string> dirs_sym = { "d", "l", "r", "u" };
    public:
    	string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole)
    	{
    		int M = maze.size();
    		if (M <= 0) return "impossible";
    		int N = maze[0].size();
    		s = { ball[0], ball[1] }, e = { hole[0], hole[1] };
    		node *root = new node(s.first, s.second, 0, dist(s, e));
    		// compare function used in priority queue, the rank of path should be considered here.
    		auto cmp = [](node *left, node *right) { return left->f > right->f || (left->f == right->f && left->path > right->path); };
    		priority_queue<node*, vector<node*>, decltype(cmp)> open_lst(cmp);
    		open_lst.push(root);
    		unordered_set<pair<int, int>> cls_lst;
    		while (!open_lst.empty())
    		{
    			auto curr = open_lst.top();
    			open_lst.pop();
    			cls_lst.insert({ curr->x, curr->y });
    			for (int i = 0; i < 4; ++i)
    			{
    				int x = curr->x, y = curr->y, step = curr->g;
    				while (x + dirs[i].first >= 0 && x + dirs[i].first < M
    					&& y + dirs[i].second >= 0 && y + dirs[i].second < N
    					&& maze[x + dirs[i].first][y + dirs[i].second] != 1
    					&& (x != e.first || y != e.second))
    				{
    					x += dirs[i].first;
    					y += dirs[i].second;
    					++step;
    				}
    				// if jump no space, ignore
    				if (step == curr->g) continue;
    				auto neighbor = new node(x, y, step, dist({ x, y }, e), curr->path + dirs_sym[i]);
    				if (x == e.first && y == e.second)
    					return neighbor->path;
    				// if visited, ignore
    				if (cls_lst.count({ x, y }))
    				{
    					delete neighbor;
    					continue;
    				}
    				open_lst.push(neighbor);
    			}
    		}
    		return "impossible";
    	}
    };
    

    I learn this algorithm from:
    http://web.mit.edu/eranki/www/tutorials/search/
    it has easy-to-understand pseudocode.
    One thing special to consider for this problem is if f is same for two nodes, the paths should be considered to rank them in priority queue.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.