vivek_ragi

OPEN_THE_LOCK

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