vivek_ragi

OPEN_THE_LOCK_MINE

Jun 11th, 2021
593
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3. public:
  4.     int openLock(vector<string>& deadends, string target) {
  5.         unordered_set<string> s;
  6.         for(auto it:deadends)
  7.             s.insert(it);
  8.        
  9.         queue<pair<string,int>> q;
  10.         q.push({"0000",0});
  11.        
  12.         unordered_map<string,bool> vis;
  13.         // vector<bool> vis(10000,false);
  14.         vis["0000"] = true;
  15.         while(!q.empty())
  16.         {
  17.             string v = q.front().first;
  18.             int level = q.front().second;
  19.             q.pop();
  20.  
  21.             if(s.count(v))
  22.                 continue;
  23.  
  24.             if(v == target){
  25.                 return level;
  26.             }
  27.             for(int j=0;j<4;j++){
  28.                 int num = v[j]-'0';
  29.                 int next = num==9?0:num+1;
  30.                 int prev = num==0?9:num-1;
  31.                 string s1 = v;
  32.                 string s2 = v;
  33.                 s1[j] = '0' + next;
  34.                 s2[j] = '0' + prev;
  35.  
  36.                 if(!vis[(s1)]){
  37.                     vis[(s1)]=true;
  38.                     q.push({(s1),level+1});
  39.                 }
  40.                 if(!vis[(s2)]){
  41.                     vis[(s2)]=true;
  42.                     q.push({(s2),level+1});
  43.                 }
  44.             }
  45.  
  46.         }
  47.  
  48.         return -1;
  49.     }
  50. };
  51.  
RAW Paste Data