1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

const int INF = 10000;
const int DEAD = 10001;

class Solution {
    int met(std::string str) {
        int res = 0;
        for (auto& c : str) {
            res *= 10;
            res += (c - '0');
        }
        return res;
    }
    
public:
    int openLock(std::vector<std::string>& deadends, std::string target) {
        std::vector<int> dist(10000, INF);
        int start = 0;
        start = met(target);
        if (start == 0) {
            return 0;
        }
        
        for (auto& str : deadends) {
            dist[met(str)] = DEAD;
        }
        std::queue<int> q;
        q.push(start);
        dist[start] = 0;
        int mods[] = { 1, 10, 100, 1000 };
        int dirs[] = { 1, 9 };
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& m : mods) {
                for (auto& dir : dirs) {
                    int r = u / (m * 10) * m * 10;
                    int v = (dir * m + (u - r)) % (m * 10) + r;
                    if (dist[v] == DEAD) {
                        continue;
                    }
                    if (v == 0) {
                        return dist[u] + 1;
                    }
                    if (dist[v] == INF) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
        }
        return -1;
    }
};