<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 stToI(std::string &s) 
    {
        return s[3] + s[2]*10 + s[1]*100 + s[0]*1000 - (int('0')*1111);
    }
    void rec(int *dist, std::vector<int> layer, int &target, int d = 0)
    {
        if(layer.empty() || dist[target] != 0) return;
        std::vector<int> nextLayer;
        int digits[4];
        for(auto i : layer)
        {
            if(dist[i] != 0) continue;
            dist[i] = d;
            //nextLayer TODO!!!
            digits[0] = i%10;
            digits[1] = i%100-digits[0];
            digits[2] = i%1000-digits[1]-digits[0];
            digits[3] = i%10000-digits[2]-digits[1]-digits[0];
            //std::cout << i << " " << digits[0] + digits[1] + digits[2] + digits[3] << " ";
            nextLayer.push_back((digits[3]+1000)%10000 + digits[2] + digits[1] + digits[0]);
            nextLayer.push_back((digits[3]+9000)%10000 + digits[2] + digits[1] + digits[0]);
            nextLayer.push_back(digits[3] + (digits[2]+100)%1000 + digits[1] + digits[0]);
            nextLayer.push_back(digits[3] + (digits[2]+900)%1000 + digits[1] + digits[0]);
            //std::cout << digits[3] + (digits[2]+900)%1000 + digits[1] + digits[0] << "\n";
            nextLayer.push_back(digits[3] + digits[2] + (digits[1]+10)%100 + digits[0]);
            nextLayer.push_back(digits[3] + digits[2] + (digits[1]+90)%100 + digits[0]);
            nextLayer.push_back(digits[3] + digits[2] + digits[1] + (digits[0]+1)%10);
            nextLayer.push_back(digits[3] + digits[2] + digits[1] + (digits[0]+9)%10);
        }
        rec(dist, nextLayer, target, d + 1);
    }
    int openLock(vector<string>& deadends, string target)
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        if(target == "0000") return 0;
        int targetI = stToI(target);
        int distI[10000] = {0};
        //std::unordered_map<std::string, int> dist;
        //dist.reserve(10000);
        //for(auto i : deadends) dist[i] = -1;
        for(auto &i : deadends) distI[stToI(i)] = -1;
        rec(distI, {0}, targetI);
        return distI[targetI] > 0 ? distI[targetI] : -1;
    }
};
37996