[Clean code] C++ BFS, 13ms solution


  • 0
    S

    Basic idea:

    1. Use an array with size "10000" to record the point which has been used. (0000 - 9999)
    vector<bool> used(10000, false);
    
    1. Put deadends in this array.
    2. Put "0000" to the BFS queue as beginning.
    3. For each point in BFS queue, put their candidate into BFS queue (Every point has 8 different possible candidates.) We also need to check the node is used or not.
    4. If we got the result in queue, return the total steps.
    5. If BFS queue is empty, it means that we could not get a solution. return -1;

    For example:
    0202 has 8 different possible candidates as following:
    1202, 9202 (First digit +1 / -1)
    0302, 0102 (Second digit +1 / -1)
    0212, 0292 (Third digit +1/-1)
    0203, 0201(Fourth digit +1/-1)

    int openLock(vector<string>& deadends, string target) {
            vector<bool> used(10000, 0);
            int targetInt = atoi(target.c_str());
            for (int i = 0; i < deadends.size(); i++)
                used[atoi(deadends[i].c_str())] = true;
            
            queue<int> bfs;
            bfs.push(0); //"0000" is beginning
            
            int result = 0;
            while (!bfs.empty()) {
                int m = bfs.size();
                for (int i = 0; i < m; i++) {
                    int frontItem = bfs.front();
                    if (!used[frontItem]) {
                        used[frontItem] = true;
                        if (frontItem == targetInt) return result;
                        // 8 possible candidates
                        bfs.push((frontItem % 10000 >= 9000) ? frontItem - 9000 : frontItem + 1000);
                        bfs.push((frontItem % 1000 >= 900) ? frontItem - 900 : frontItem + 100);
                        bfs.push((frontItem % 100 >= 90) ? frontItem - 90 : frontItem + 10);
                        bfs.push((frontItem % 10 >= 9) ? frontItem - 9 : frontItem + 1);
                        bfs.push((frontItem % 10000 < 1000) ? frontItem + 9000 : frontItem - 1000);
                        bfs.push((frontItem % 1000 < 100) ? frontItem + 900 : frontItem - 100);
                        bfs.push((frontItem % 100 < 10) ? frontItem + 90 : frontItem - 10);
                        bfs.push((frontItem % 10 < 1) ? frontItem + 9 : frontItem - 1);
                    }
                    bfs.pop();
                }
                result++;
            }
            return -1;
        }
    

Log in to reply
 

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