Easy to Understand(BFS+queue)


  • 0
    G

    C++:
    First, extend(int) helps us explore the next states. Then, queue is used to store the valid states.
    '''

    vector<int> extend(int x){
        vector<int> ans;
        int t = 1;
        for(int i = 0; i< 4; ++i){
            int w = x/t%10;
            ans.push_back(x-w*t+(w+1)%10*t);
            ans.push_back(x-w*t+(w+9)%10*t);
            t*=10;
        }
        return ans;
    }
    int openLock(vector<string>& deadends, string target) {
    
        vector<bool> states(10000, false);
        
        for(int i = 0; i< deadends.size(); i++){
            string d = deadends[i];
            int x = (d[0]-'0')*1000 + (d[1] - '0')*100 + (d[2] - '0')*10 + (d[3] - '0');
            states[x] = true;
        }
        
        int t = (target[0] - '0')*1000 + (target[1] - '0')*100 + (target[2] - '0')*10 + (target[3] - '0');
        queue<int> q;
        if(!states[0]) q.push(0);
        states[0] =  true;
        int ans = -1;
        int step = 0;
        while(!q.empty()){
            int n = q.size();
            while(n--){
                int x = q.front(); q.pop();
                if(x == t) { ans = step; break;}
                vector<int> vec = extend(x);
                for(int i = 0; i<8; ++i){
                    if(!states[vec[i]]){
                        states[vec[i]] = true;
                        q.push(vec[i]);
                    }
                    
                }
            }
            if(ans >= 0) break; step++;
        }
        return ans;
    }

Log in to reply
 

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