6ms c++ dfs using stack


  • 0
    H

    I use stack to solve this problem. It works well. However, I think this code may have problems in some cases.

    In general, I store the index in vector stones in pair.first and the last step distance in pair.second.

    
    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            int end=stones.size();
            if(stones[1]!=1) return false;
            if(end==2) return true;
            stack<pair<int,int>> stk;
            stk.push(make_pair(1,1));
            while(!stk.empty()){
                pair<int,int> p1=stk.top();
                stk.pop();
                for(int i=p1.first+1;i<end;i++){
                    if(stones[i]-stones[p1.first]>p1.second+1){
                        if(stones[i]>2*stones[p1.first]+10)   //use it to pass the corner case. eg,  1,2,3,4,5,6,7,8,....,1000,99999999, 
    // without this judgement, it will get TLE. Still, in some cases, it may have some problems. 
    //But it can be solve it by changing "if condition" using math .
                            return false;
                        break;
                    }
                    if(stones[i]-stones[p1.first]>=p1.second-1){
                        if(i==end-1) return true;
                        stk.push(make_pair(i,stones[i]-stones[p1.first]));
                    }
                }
            }
            return false;
            
        }
    };
    

Log in to reply
 

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