1
class Solution {
2
 public:
3
  int openLock(vector<string> &deadends, string target) {
4
    if (target == "0000") return 0;
5
    queue<int> queue;
6
    queue.push(0);
7
    bool seen[10000]{false};
8
    for (auto &d : deadends) seen[stoi(d)] = true;
9
    int targ = stoi(target);
10
    if (seen[0]) return -1;
11
    for (int turns = 1; queue.size(); turns++) {
12
      int qlen = queue.size();
13
      for (int i = 0; i < qlen; i++) {
14
        int curr = queue.front();
15
        queue.pop();
16
        for (int j = 1; j < 10000; j *= 10) {
17
          int mask = curr % (j * 10) / j, masked = curr - (mask * j);
18
          for (int k = 1; k < 10; k += 8) {
19
            int next = masked + (mask + k) % 10 * j;
20
            if (seen[next]) continue;
21
            if (next == targ) return turns;
22
            seen[next] = true;
23
            queue.push(next);
24
          }
25
        }
26
      }
27
    }
28
    return -1;
29
  }
30
};