C++ A* search for Maze II and III


  • 0
    struct node
    {
    	int x, y;
    	int g;
    	int h;
    	int f;
    	node() = default;
    	node(int xx, int yy, int gg, int hh) 
    		: x(xx), y(yy), g(gg), h(hh){ f = g + h;	}
    };
    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:
    	int cal(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 } };
    public:
    	int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination)
    	{
    		int M = maze.size();
    		if (M <= 0) return -1;
    		int N = maze[0].size();
    		s = { start[0], start[1] }, e = { destination[0], destination[1] };
    		node *root = new node(s.first, s.second, 0, cal(s, e));
    		// compare function for heap
    		auto cmp = [](node *left, node *right) { return left->f > right->f; };
    		priority_queue<node*, vector<node*>, decltype(cmp)> open_lst(cmp);
    		open_lst.push(root);
    		vector<vector<int>> dist(M, vector<int>(N, -1));
    		dist[s.first][s.second] = 0;
    		// visited node
    		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 (auto &dir : dirs)
    			{
    				int x = curr->x, y = curr->y, step = curr->g;
    				while (x + dir.first >= 0 && x + dir.first < M
    					&& y + dir.second >= 0 && y + dir.second < N
    					&& maze[x + dir.first][y + dir.second] != 1)
    				{
    					x += dir.first;
    					y += dir.second;
    					++step;
    				}
    				// if jump no space || visited || not a better path
    				if (step == curr->g || cls_lst.count({ x, y }) || (dist[x][y] != -1 && step >= dist[x][y])) continue;
    				if (x == e.first && y == e.second)
    					return step;
    				auto neighbor = new node(x, y, step, cal({ x, y }, e));
    				dist[x][y] = step;
    				open_lst.push(neighbor);
    			}
    		}
    		return -1;
    	}
    };
    

    Here is my A* solution to maze III
    https://discuss.leetcode.com/topic/85478/ac-c-6ms-a-search


Log in to reply
 

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