<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:
  
    char sp1(char a)
    {
        if(a == '0')
        {
            return '9';
        }
        if(a == '1')
        {
            return '0';
        }
        if(a == '2')
        {
            return '1';
        }
        if(a == '3')
        {
            return '2';
        }
        if(a == '4')
        {
            return '3';
        }
        if(a == '5')
        {
            return '4';
        }
        if(a == '6')
        {
            return '5';
        }
        if(a == '7')
        {
            return '6';
        }
        if(a == '8')
        {
            return '7';
        }
        if(a == '9')
        {
            return '8';
        }  

        return '1';
    }
    char sp2(char a)
    {
        if(a == '0')
        {
            return '1';
        }
        if(a == '1')
        {
            return '2';
        }
        if(a == '2')
        {
            return '3';
        }
        if(a == '3')
        {
            return '4';
        }
        if(a == '4')
        {
            return '5';
        }
        if(a == '5')
        {
            return '6';
        }
        if(a == '6')
        {
            return '7';
        }
        if(a == '7')
        {
            return '8';
        }
        if(a == '8')
        {
            return '9';
        }
        if(a == '9')
        {
            return '0';
        }  

        return '1';
    }



    int openLock(vector<string>& deadends, string target) {
        
        
        if(find(deadends.begin(),deadends.end(),"0000") != deadends.end())
        {
            return -1;
        }
        
        unordered_map<string,int> f;
        for(auto ch : deadends)
        {
            f[ch] = 1;
        }

        
        queue<pair<int,string>> q;
        q.push({0,"0000"});
        unordered_map<string,int> mp;
        mp["0000"] = 1;

        int ans = INT_MAX;
        while(!q.empty())
        {
            auto p = q.front(); q.pop();
            int st = p.first;
            string s = p.second;

            if(s == target)
            {
                ans = min(ans,st);
                continue;
            }

            for(int i = 0 ;  i < 4; i++)
            {
                // s[i] - 1
                // s[i] + 1
                char o = s[i];
                char ch1 = sp1(o);
                s[i] = ch1;
                if(f.find(s)== f.end())
                {
                    if(mp.find(s) == mp.end())
                    {
                        mp[s] = 1;
                        q.push({st+1,s});
                    }
                }
                char ch2 = sp2(o);
                s[i] = ch2;
                if(f.find(s) == f.end())
                {
                    if(mp.find(s) == mp.end())
                    {
                        mp[s] = 1;
                        q.push({st+1,s});
                    }
                }
                s[i] = o;
            }

        }

        return ans == INT_MAX ? -1 : ans;

    }
};
91396