<p>You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: <code>&#39;0&#39;, &#39;1&#39;, &#39;2&#39;, &#39;3&#39;, &#39;4&#39;, &#39;5&#39;, &#39;6&#39;, &#39;7&#39;, &#39;8&#39;, &#39;9&#39;</code>. The wheels can rotate freely and wrap around: for example we can turn <code>&#39;9&#39;</code> to be <code>&#39;0&#39;</code>, or <code>&#39;0&#39;</code> to be <code>&#39;9&#39;</code>. Each move consists of turning one wheel one slot.</p>

<p>The lock initially starts at <code>&#39;0000&#39;</code>, a string representing the state of the 4 wheels.</p>

<p>You are given a list of <code>deadends</code> dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.</p>

<p>Given a <code>target</code> representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;0201&quot;,&quot;0101&quot;,&quot;0102&quot;,&quot;1212&quot;,&quot;2002&quot;], target = &quot;0202&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> 
A sequence of valid moves would be &quot;0000&quot; -&gt; &quot;1000&quot; -&gt; &quot;1100&quot; -&gt; &quot;1200&quot; -&gt; &quot;1201&quot; -&gt; &quot;1202&quot; -&gt; &quot;0202&quot;.
Note that a sequence like &quot;0000&quot; -&gt; &quot;0001&quot; -&gt; &quot;0002&quot; -&gt; &quot;0102&quot; -&gt; &quot;0202&quot; would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end &quot;0102&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;8888&quot;], target = &quot;0009&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can turn the last wheel in reverse to move from &quot;0000&quot; -&gt; &quot;0009&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;8887&quot;,&quot;8889&quot;,&quot;8878&quot;,&quot;8898&quot;,&quot;8788&quot;,&quot;8988&quot;,&quot;7888&quot;,&quot;9888&quot;], target = &quot;8888&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> We cannot reach the target without getting stuck.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= deadends.length &lt;= 500</code></li>
	<li><code>deadends[i].length == 4</code></li>
	<li><code>target.length == 4</code></li>
	<li>target <strong>will not be</strong> in the list <code>deadends</code>.</li>
	<li><code>target</code> and <code>deadends[i]</code> consist of digits only.</li>
</ul>

class Solution {
public:
    int a_star(vector<string>& deadends, string target) {
        const string start = "0000";
        std::unordered_set<string> fast_deadends{deadends.begin(), deadends.end()};
        
        for (const auto& notable : {start, target}) {
            if (fast_deadends.count(notable) > 0) {
                return -1;
            }
        }

        std::unordered_map<char, char> increment = {{'0', '1'}, {'1', '2'}, {'2', '3'}, {'3', '4'}, {'4','5'}, {'5', '6'}, {'6', '7'}, {'7', '8'}, {'8', '9'}, {'9', '0'}};
        std::unordered_map<char, char> decrement = {{'0', '9'}, {'1', '0'}, {'2', '1'}, {'3', '2'}, {'4','3'}, {'5', '4'}, {'6', '5'}, {'7', '6'}, {'8', '7'}, {'9', '8'}};

        auto expand = [&fast_deadends, &increment, &decrement](const string& x) {
            vector<string> candidates;
            for (size_t i = 0; i < 4; ++i) {
                {
                    string candidate = x;
                    candidate[i] = increment.at(x[i]);
                    if (fast_deadends.count(candidate) == 0) {
                        candidates.push_back(candidate);
                    }
                }

                {
                    string candidate = x;
                    candidate[i] = decrement.at(x[i]);
                    if (fast_deadends.count(candidate) == 0) {
                        candidates.push_back(candidate);
                    }
                }
            }
            return candidates;
        };

        auto manhattan_distance = [](const string& x, const string& y) {
            int distance = 0;
            for (size_t i = 0; i < 4; ++i) {
                int dx = x[i] - '0';
                int dy = y[i] - '0';
                distance += min(abs(dx - dy), 10 - abs(dx - dy));
            }
            return distance;
        };

        unordered_map<string, int> costToCome;
        auto c = [&costToCome](const string& x) {
            return costToCome.count(x) > 0 ? costToCome[x] : numeric_limits<int>::max();
        };

        auto compare = [&c, &manhattan_distance, &target](const string& x, const string& y) {
            return c(x) + manhattan_distance(x, target) > c(y) + manhattan_distance(y, target);
        };
        priority_queue<string, vector<string>, decltype(compare)> queue(compare);

        queue.push(start);
        costToCome[start] = 0;

        bool done = false;
        while (!queue.empty() && !done) {
            const auto x = queue.top();
            queue.pop();

            if (x == target) {
                done = true;
            }

            for (const auto& candidate : expand(x)) {
                const auto newCost = c(x) + 1;
                if (newCost < min(c(target), c(candidate))) {
                    costToCome[candidate] = newCost;
                    if (candidate != target) {
                        queue.push(candidate);
                    }
                }
            }
        }

        if (c(target) == numeric_limits<int>::max()) {
            return -1;
        }

        return c(target);

    }
    int openLock(vector<string>& deadends, string target) {
        return a_star(deadends, target);
    }
};
136453