<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) {
        unordered_map<string, bool> isDeadend;
        for(int i=0;i<deadends.size();i++){
            isDeadend[deadends[i]] = true;
        }
        vector<bool> isVisited(10000, false);
        queue< pair<string, int> > q;
        if(isDeadend["0000"])
            return -1;
        q.push({"0000",0});
    
        while(!q.empty()){
            auto [currentNum, turns] = q.front();
            q.pop();
            if(currentNum == target)
                return turns;
            for(int i=0;i<4;i++){
                int toChangeNum = currentNum[i] - '0';
                int prevNum = (toChangeNum-1) < 0 ? 9 : toChangeNum-1;
                int nextNum = (toChangeNum+1) > 9 ? 0 : toChangeNum+1;
                string tempPrev = currentNum, tempNext = currentNum;
                tempPrev[i] = prevNum + '0';
                tempNext[i] = nextNum + '0';
                if(!isVisited[stoi(tempPrev)] && !isDeadend[tempPrev]){
                    isVisited[stoi(tempPrev)] = true;
                    q.push({tempPrev,turns+1});
                }
                if(!isVisited[stoi(tempNext)] && !isDeadend[tempNext]){
                    isVisited[stoi(tempNext)] = true;
                    q.push({tempNext,turns+1});
                }
             }
        }
        return -1;
    }
};
// #include <iostream>
// #include <unordered_map>
// #include <vector>
// #include <queue>
// using namespace std;

class Solution1 {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_map<string, bool> isDeadend;
        for(int i=0; i<deadends.size(); i++){
            isDeadend[deadends[i]] = true;
        }

        vector<bool> isVisited(10000, false);
        queue< pair<string, int> > q;
        q.push({"0000", 0});

        while(!q.empty()) {
            auto [currentNum, turns] = q.front();
            q.pop();

            // Debugging: print the current state and number of turns
            cout << "Current: " << currentNum << ", Turns: " << turns << endl;

            if (currentNum == target) 
                return turns;

            for (int i = 0; i < 4; i++) {
                int toChangeNum = currentNum[i] - '0';  // Convert char to int
                int prevNum = (toChangeNum - 1) < 0 ? 9 : toChangeNum - 1;
                int nextNum = (toChangeNum + 1) > 9 ? 0 : toChangeNum + 1;

                string tempPrev = currentNum, tempNext = currentNum;
                tempPrev[i] = char(prevNum + '0');
                tempNext[i] = char(nextNum + '0');

                // Debugging: print the previous and next numbers being considered
                cout << "Prev: " << tempPrev << ", Next: " << tempNext << endl;

                if (!isVisited[stoi(tempPrev)] && !isDeadend[tempPrev]) {
                    isVisited[stoi(tempPrev)] = true;
                    q.push({tempPrev, turns + 1});
                    // Debugging: print when adding to the queue
                    cout << "Pushed to queue: " << tempPrev << " with turns " << turns + 1 << endl;
                }

                if (!isVisited[stoi(tempNext)] && !isDeadend[tempNext]) {
                    isVisited[stoi(tempNext)] = true;
                    q.push({tempNext, turns + 1});
                    // Debugging: print when adding to the queue
                    cout << "Pushed to queue: " << tempNext << " with turns " << turns + 1 << endl;
                }
            }
        }
        return -1;
    }
};

48009