AC A* search solution


  • 0
    struct node
    {
    	string board;
    	unordered_map<char, int> dict;
    	int g; // balls used
    	int f;
    	int balls;
    	node() = default;
    	node(string b, unordered_map<char, int> d, int depth, int c) 
    		: board(b), dict(d), g(depth), balls(c)
    	{ 
    		unordered_set<char> s;
    		for (auto c : board) s.insert(c);
    		f = g + heurist();
    	};
    	int heurist()
    	{
    		unordered_set<char> s;
    		for (auto c : board) s.insert(c);
    		return board.length() * s.size();
    	}
    };
    class Solution 
    {
    private:
    	void erase_3(string &s, int pos)
    	{
    		int start = pos;
    		for (; start >= 0 && s[start] == s[pos]; --start);
    		if (start == pos - 1) return;
    		int end = pos;
    		for (; end < s.length() && s[end] == s[pos]; ++end);
    		if (end - ++start >= 3)
    		{
    			s.erase(start, end - start);
    			erase_3(s, start);
    		}
    	}
    public:
    	int findMinStep(string board, string hand) 
    	{
    		unordered_map<char, int> dict;
    		for (auto &c : hand) ++dict[c];
    		node *root = new node(board, dict, 0, hand.length());
    		auto cmp = [](node *lhs, node *rhs) { return lhs->f > rhs->f; };
    		priority_queue<node*, vector<node*>, decltype(cmp)> open_lst(cmp);
    		open_lst.push(root);
    		unordered_map<string, int> dist;
    		dist[board] = 0;
    		unordered_set<string> cls_lst;
    		while (!open_lst.empty())
    		{
    			auto curr = open_lst.top();
    			open_lst.pop();
    			cls_lst.insert(curr->board);
    			string b = curr->board;
    			for (int i = 0; i < b.length();)
    			{
    				int count = 1;
    				while (i + count < b.length() && b[i] == b[i + count])
    					++count;
    				if (curr->dict[b[i]] < 3 - count)
    				{
    					i += count;
    					continue;
    				}
    				int gap = 3 - count; // balls would be used
    				string tmp = b;
    				tmp.erase(i, count);
    				curr->dict[b[i]] -= gap;
    				erase_3(tmp, i);
    				if (tmp.empty())
    					return curr->g + 3 - count;
    				auto neighbor = 
    					new node(tmp, curr->dict, curr->g + gap, curr->balls - gap);
    				curr->dict[b[i]] += gap;
    				i += count;
    				if (cls_lst.count(tmp)
    				|| (dist.count(tmp) && dist[tmp] <= neighbor->g)
    				|| neighbor->balls == 0)
    				{
    					delete neighbor;
    					continue;
    				}
    				dist[tmp] = neighbor->g;
    				open_lst.push(neighbor);
    			}
    		}
    		return -1;
    	}
    };
    

    I will try to make it more concise.


  • 0
    This post is deleted!

Log in to reply
 

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