752.md

752. Open the Lock

Solution 1 (time O(10^4), space O(10^4))

# BFS
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if (target == "0000") {
            return 0;
        }
        bool vis[10000];
        for (int i = 0; i < 10000; i++) {
            vis[i] = false;
        }
        for (int i = 0; i < deadends.size(); i++) {
            vis[stoi(deadends[i])] = true;
        }
        if (vis[0] == true) {
            return -1;
        }
        queue <pair <string, int>> q;
        q.push(make_pair("0000", 0));
        vis[0] = true;
        while (!q.empty()) {
            pair <string, int> cur_pair = q.front();
            q.pop();
            string cur_slot = cur_pair.first;
            int cur_level = cur_pair.second;
            string new_slot;
            for (int i = 0; i < 4; i++) {
                new_slot = cur_slot;
                if (new_slot[i] == '9') {
                    new_slot[i] = '0';
                } else {
                    new_slot[i] = new_slot[i] + 1;
                }
                if (new_slot == target) {
                    return cur_level + 1;
                }
                if (vis[stoi(new_slot)] == false) {
                    vis[stoi(new_slot)] = true;
                    q.push(make_pair(new_slot, cur_level + 1));
                }
                new_slot = cur_slot;
                if (new_slot[i] == '0') {
                    new_slot[i] = '9';
                } else {
                    new_slot[i] = new_slot[i] - 1;
                }
                if (new_slot == target) {
                    return cur_level + 1;
                }
                if (vis[stoi(new_slot)] == false) {
                    vis[stoi(new_slot)] = true;
                    q.push(make_pair(new_slot, cur_level + 1));
                }
            }
        }
        return -1;
    }
};