<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>

#include <iostream>

class Solution {
    
private:
    
    vector<string>& getValidNeighbors(string starting_node, set<string>& deadends_set, set<string>& explored_set){
        vector<string> *neighbors = new vector<string>;
        
        // For each digit you can move both forward and backward:
        int digit, next_digit, pre_digit = -1;
        string pre_comb, next_comb;
        char digit_char;
        bool is_deadend;
        
        for(int i = 0; i < starting_node.length(); i++){
            
            digit_char = starting_node[i];
            
            digit = int(digit_char - '0');
            pre_digit = (digit - 1 + 10) % 10;
            next_digit = (digit + 1) % 10;
            
            //cout<<"Digit: "<<digit<<" Pre: "<<pre_digit<<" Next: "<<next_digit<<endl;
            
            pre_comb = starting_node;
            next_comb = starting_node;
            
            pre_comb[i] = char(pre_digit  + int('0'));
            next_comb[i] = char(next_digit  + int('0'));
            //cout<<"Comb: "<<starting_node<<" Pre-comb: "<<pre_comb<<" Next-comb: "<<next_comb<<endl;
            

            if(deadends_set.find(pre_comb) == deadends_set.end() &
               explored_set.find(pre_comb) == explored_set.end() ){
                neighbors->push_back(pre_comb);
                explored_set.insert(pre_comb);
            }
            
            if(deadends_set.find(next_comb) == deadends_set.end() &
               explored_set.find(next_comb) == explored_set.end() ){
                neighbors->push_back(next_comb);
                explored_set.insert(next_comb);
            }
        }
        
        return *neighbors;
    }
    
    
    
    
    
public:
    int openLock(vector<string>& deadends, string target) {
        
        set<string> deadends_set;
        for(auto deadend:deadends){
            deadends_set.insert(deadend);
        }
        
        /*
        vector<string> neighbors;
        neighbors = getValidNeighbors("0101", deadends_set);
        
        cout<<"Neigbors of starting node:"<<endl;
        for(auto neighbor:neighbors){
            cout<<neighbor<<endl;
        }*/
        
        string root_string = "0000";
        if(target == root_string) return 0;
        if(deadends_set.find(root_string) != deadends_set.end()) return -1;

        // Regular BFS from starting node: stop if target is reached in neighbırs 
        queue<pair<string, int>> nodes_q;
        nodes_q.push(make_pair(root_string, 0));
        
        pair<string, int> current_pair;
        string current_comb;
        vector<string> neighbors;
        

        set<string> explored_set;
        explored_set.insert(root_string);
        
        while(!nodes_q.empty()){
            
            current_pair = nodes_q.front();
            current_comb = current_pair.first;
            nodes_q.pop();
            
            neighbors = getValidNeighbors(current_comb, deadends_set, explored_set);
            
            for(auto neighbor:neighbors){
                if(neighbor == target){
                    return current_pair.second + 1;
                }
                nodes_q.push(make_pair(neighbor, current_pair.second + 1));
            }

        }
          
        return -1;
        
    }
};
56353