<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 turnUpDown(int num, int pos, bool isUp) {
        string n = to_string(num);
        if (n.length() < 4) {
            n.insert(0, 4 - n.length(), '0');
        }

        if (isUp) { //Up
            if (n[pos] == '9') {
                n[pos] = '0';
            } else {
                n[pos] += 1;
            }
        } else { //Down
            if (n[pos] == '0'){
                n[pos] = '9';
            } else {
                n[pos] -= 1;
            }
        }

        return stoi(n);
    }

    int openLock(vector<string>& deadends, string target) {
        vector<vector<int>> w(10000);
        vector<bool> dead(10000, false);
        vector<bool> vis(10000, false);
        int tar = stoi(target);

        for (int i = 0; i < deadends.size(); i++) {
            int intDead = stoi(deadends[i]);
            // cout << "intDead: " << intDead << endl;
            dead[intDead] = true;
        }

        // for(int i = 0; i < 10000; i++){
        //     for(int j = 0; j < 4; j++){
        //         int up = turnUpDown(i, j, true);
        //         int down = turnUpDown(i, j, false);
        //         w[i].push_back(up);
        //         w[i].push_back(down);
        //         // w[up].push_back(i);
        //         // w[down].push_back(i);
        //     }
        // }


        // for(int i = 9000; i < 9001; i++){
        //     cout << i << ": ";
        //     for(int j = 0; j < w[i].size(); j++){
        //         cout << w[i][j] << " ";
        //     }
        //     cout << endl;
        // }

        if(dead[0]){
            return -1;
        }
        if(tar == 0){
            return 0;
        }

        queue<pair<int, int>> q;
        q.push({0, 0});
        vis[0] = true;

        // while(!q.empty()){
        //     int u = q.front().first;
        //     int d = q.front().second;
        //     q.pop();

        //     for(int x : w[u]){

        //         if(x == tar){
        //             return d + 1;
        //         }

        //         if(!vis[x] && !dead[x]){
        //             q.push({x, d + 1});
        //             vis[x] = true;
        //         }
        //     }
        // }

        while(!q.empty()){
            int u = q.front().first;
            int d = q.front().second;
            q.pop();

            for(int k = 0; k < 4; k++){
                int up = turnUpDown(u, k, true);
                int down = turnUpDown(u, k, false);

                if(up == tar || down == tar){
                    return d + 1;
                }

                if(!vis[up] && !dead[up]){
                    q.push({up, d + 1});
                    vis[up] = true;
                }

                if(!vis[down] && !dead[down]){
                    q.push({down, d + 1});
                    vis[down] = true;
                }
            }
        }

        return -1;
    }
};
27984