BFS solution C++


  • 8

    Every node has 8 edges. The nodes in dead ends cannot be visited. Find the shortest path from the initial node to the target.

    class Solution {
    public:
        int openLock(vector<string>& deadends, string target) {
            unordered_set<string> dds(deadends.begin(), deadends.end());
            unordered_set<string> visited;
            queue<string> bfs;
            string init = "0000";
            if (dds.find(init) != dds.end()) return -1;
            visited.insert("0000");
            bfs.push("0000");
            int res = 0;
            while (!bfs.empty()) {
                int sz = bfs.size();
                for (int i = 0; i < sz; i++) {
                    string t = bfs.front(); bfs.pop();
                    vector<string> nbrs = move(nbrStrs(t));
                    for (auto s : nbrs) {
                        if (s == target) return ++res;
                        if (visited.find(s) != visited.end()) continue;
                        if (dds.find(s) == dds.end()) {
                            bfs.push(s);
                            visited.insert(s);
                        }
                    }
                }
                ++res;
            }
            return -1;
        }
        
        
        vector<string> nbrStrs(string key) {
            vector<string> res;
            for (int i = 0 ; i < 4; i++) {
                string tmp = key;
                tmp[i] = (key[i] - '0' + 1) % 10 + '0';
                res.push_back(tmp);
                tmp[i] = (key[i] - '0' - 1 + 10) % 10 + '0';
                res.push_back(tmp);
             }
            return res;
        }
    };
    

    Bidirectional BFS improves the efficiency

        int openLock(vector<string>& deadends, string target) {
            unordered_set<string> dds(deadends.begin(), deadends.end());
            unordered_set<string> q1, q2, pass, visited;
            string init = "0000";
            if (dds.find(init) != dds.end() || dds.find(target) != dds.end()) return -1;
            visited.insert("0000");
            q1.insert("0000"), q2.insert(target);
            int res = 0;
            while (!q1.empty() && !q2.empty()) {
                if (q1.size() > q2.size()) swap(q1, q2);
                pass.clear();
                for (auto ss : q1) {
                    vector<string> nbrs = nbrStrs(ss);
                    for (auto s : nbrs) {
                        if (q2.find(s) != q2.end()) return res + 1;
                        if (visited.find(s) != visited.end()) continue;
                        if (dds.find(s) == dds.end()) {
                            pass.insert(s);
                            visited.insert(s);
                        }
                    }
                }
                swap(q1, pass);
                res++;
            }
            return -1;
        }
    

  • 0
    N

    @enigmaJY did it get accepted? I tried similar approach and it ran into time limit error.


  • 0

    @nragrawal accepted


  • 0
    A
    This post is deleted!

  • 0
    L

    Nice solution. Could you please emphasize what exactly is move() doing here? I haven't used/seen it being used ever before. Thanks!


  • 0

    @lkjhgfdsa It is a move constructor. If you use a copy constuctor there, it will get accepted as well.


  • 0
    S

    @lkjhgfdsa c++'s std::move


  • 0
    J

    How come is 16 edges? I thought each digit has three choices: +1, -1, remain the same...
    doesn't it?

    Shouldn't it be 3^4 - 1 = 80 edges? (81 minus the one situation that all digits remain the same)


  • 0

    @jackyuan.jack You have 4 circular wheels. In every operation, you choose one wheel to rotate and can rotate towards 2 directions. Should be 4 * 2 edges. Thanks for correction.


  • 1
    W

    hash set "dds" and "visited" can actually be merged to simplify the code.
    Nice solution anyway, especially the bidirectional bfs.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.