<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 {
    using LockSetting = std::array<uint8_t, 4>;
    LockSetting toLockSetting(string s) {
        return {
            static_cast<uint8_t>(s[0] - '0'),
            static_cast<uint8_t>(s[1] - '0'),
            static_cast<uint8_t>(s[2] - '0'),
            static_cast<uint8_t>(s[3] - '0')
        };
    }
 
    string toString(const LockSetting& setting) {
        string ret = string() +
            static_cast<char>('0' + setting[0]) +
            static_cast<char>('0' + setting[1]) +
            static_cast<char>('0' + setting[2]) +
            static_cast<char>('0' + setting[3]);
        return ret;
    }
 
    static inline uint8_t mod10(uint8_t x) {
        return x - (x >= 10) * 10;
    }
 
    static uint8_t distance(const LockSetting& a, const LockSetting& b) {
        constexpr auto dist1 = [](uint8_t a1, uint8_t b1) {
            constexpr uint8_t dmap[] = { 1, 2, 3, 4, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 };
            uint8_t d1 = 9 + a1 - b1;
            return dmap[d1];
        };
        return dist1(a[0], b[0])
            + dist1(a[1], b[1])
            + dist1(a[2], b[2])
            + dist1(a[3], b[3]);
    }
 
    static std::array<LockSetting, 8> neighbors(LockSetting ls) {
        constexpr uint8_t next[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
        constexpr uint8_t prev[] = { 9, 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        return {
            LockSetting{next[ls[0]], ls[1], ls[2], ls[3]},
            LockSetting{prev[ls[0]], ls[1], ls[2], ls[3]},
            LockSetting{ls[0], next[ls[1]], ls[2], ls[3]},
            LockSetting{ls[0], prev[ls[1]], ls[2], ls[3]},
            LockSetting{ls[0], ls[1], next[ls[2]], ls[3]},
            LockSetting{ls[0], ls[1], prev[ls[2]], ls[3]},
            LockSetting{ls[0], ls[1], ls[2], next[ls[3]]},
            LockSetting{ls[0], ls[1], ls[2], prev[ls[3]]},
        };
    }
 
public:
    int openLock(vector<string>& deadendsStr, string targetStr) {
        using Visited = std::set<LockSetting>;
        auto visited_fwd = Visited{};
        auto visited_rev = Visited{};
        for (auto& str : deadendsStr) {
            visited_fwd.insert(toLockSetting(str));
            visited_rev.insert(toLockSetting(str));
        }
 
        auto start = LockSetting{ 0, 0, 0, 0 };
        auto target = toLockSetting(targetStr);
 
        auto comp1 = [target](const auto& a, const auto& b) {
            auto distA = a.second + distance(a.first, target);
            auto distB = b.second + distance(b.first, target);
            auto eq = (distA == distB);
            return eq * (a.second < b.second) + (1 - eq) * (distA > distB);
        };
        auto comp2 = [start](const auto& a, const auto& b) {
            auto distA = a.second + distance(a.first, start);
            auto distB = b.second + distance(b.first, start);
            auto eq = (distA == distB);
            return eq * (a.second < b.second) + (1 - eq) * (distA > distB);
        };
 
        using Queue1 = std::priority_queue<
            std::pair<LockSetting, uint8_t>,
            std::vector<std::pair<LockSetting, uint8_t>>,
            decltype(comp1)>;
        using Queue2 = std::priority_queue<
            std::pair<LockSetting, uint8_t>,
            std::vector<std::pair<LockSetting, uint8_t>>,
            decltype(comp2)>;
 
        auto queue_fwd = Queue1(comp1);
        auto queue_rev = Queue2(comp2);
        queue_fwd.emplace(start, 0);
        queue_rev.emplace(target, 0);
 
        while (!(queue_fwd.empty() || queue_rev.empty())) {
            auto [setting_fwd, dist_fwd] = queue_fwd.top();
            queue_fwd.pop();
            if (setting_fwd == target) return dist_fwd;
            if (visited_fwd.contains(setting_fwd)) continue;
            visited_fwd.insert(setting_fwd);
 
            for (LockSetting next : neighbors(setting_fwd)) {
                queue_fwd.emplace(next, dist_fwd + 1);
            }
 
            auto [setting_rev, dist_rev] = queue_rev.top();
            queue_rev.pop();
            if (setting_rev == start) return dist_rev;
            if (visited_rev.contains(setting_rev)) continue;
            visited_rev.insert(setting_rev);
 
            for (LockSetting next : neighbors(setting_rev)) {
                queue_rev.emplace(next, dist_rev + 1);
            }
        }
 
        return -1;
    }
};
16303