fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_set>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. int openLock(vector<string>& deadends, string target) {
  9.     unordered_set<string> dead(deadends.begin(), deadends.end());
  10.     unordered_set<string> visited;
  11.  
  12.     // Check if the initial state is a deadend or the target itself.
  13.     if (dead.find("0000") != dead.end()) return -1;
  14.     if (target == "0000") return 0;
  15.  
  16.     // BFS setup
  17.     queue<pair<string, int>> q;
  18.     q.push({"0000", 0});
  19.     visited.insert("0000");
  20.  
  21.     while (!q.empty()) {
  22.         string curr = q.front().first;
  23.         int steps = q.front().second;
  24.         q.pop();
  25.  
  26.         // Try all possible moves
  27.         for (int i = 0; i < 4; ++i) {
  28.             for (int d = -1; d <= 1; d += 2) {  // -1 for decrement, +1 for increment
  29.                 string next = curr;
  30.                 next[i] = (next[i] - '0' + d + 10) % 10 + '0';  // rotate the i-th digit
  31.                 if (next == target) return steps + 1;  // Target found
  32.                 if (dead.find(next) == dead.end() && visited.find(next) == visited.end()) {
  33.                     visited.insert(next);
  34.                     q.push({next, steps + 1});
  35.                 }
  36.             }
  37.         }
  38.     }
  39.  
  40.     return -1;  // No solution found
  41. }
  42.  
  43. int main() {
  44.     int n;
  45.     cin >> n;
  46.     vector<string> deadends(n);
  47.     for (int i = 0; i < n; ++i) {
  48.         cin >> deadends[i];
  49.     }
  50.     string target;
  51.     cin >> target;
  52.     cout << openLock(deadends, target) << endl;
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
0201
0101
0102
1212
2002
0202
0202
stdout
copy 
6
https://ideone.com/AKjnnO
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!