<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 openLock(vector<string>& deadends, string target) {
        if (target == "0000")
            return 0;
        for (string dead : deadends)
        {
            if (dead == "0000")
                return -1;
        }
        queue<string> state;
        unordered_map<string, int> steps;
        steps["0000"] = 0;
        state.push("0000");
        while (state.size() > 0)
        {
            string current = state.front();
            cout << "current: " << current << endl;
            state.pop();
            vector<string> neighbors = generate(current);
            for (string next : neighbors)
            {
                if (steps.count(next) > 0)
                    continue;
                if (next == target)
                    return steps[current]+1;
                bool flag = true;
                for (string dead : deadends)
                {
                    if (next == dead)
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    state.push(next);
                    steps[next] = steps[current]+1;
                    cout << next << "," << steps[current]+1 << " ";
                }
            }
            cout << endl;
        }
        return -1;
    }
    
    vector<string> generate(string state)
    {
        vector<string> neighbors;
        for (int digit = 0; digit < 4; digit++)
        {
            string next1 = state, next2 = state;
            next1[digit] = (next1[digit] - 38 + 1) % 10 + 48;
            next2[digit] = (next2[digit] - 38 - 1) % 10 + 48;
            neighbors.push_back(next1);
            neighbors.push_back(next2);
        }
        return neighbors;
        
        /*
        
        int place[4] = {-1, -1, -1, -1};
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                for (int k = -1; k <= 1; k++)
                {
                    for (int p = -1; p <= 1; p++)
                    {
                        if (i || j || k || p)
                        {
                            string next = state;
                            int place[4] = {i, j, k, p};
                            for (int digit = 0; digit < 4; digit++)
                            {
                                next[digit] = (next[digit] - 38 + place[digit]) % 10 + 48;
                            }
                            neighbors.push_back(next);
                        }
                        
                    }
                }
            }
        }
        return neighbors;
        */
    }
    
};
124771