C++ DP solution


  • 0
    H
    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            if(stones.size() <= 1)
                return true;
            if(stones.size() == 2)
                return stones.back() == stones[0] + 1;
            if(stones[1] != stones[0] + 1)
                return false;
            map<int, set<int> > result;
            set<int> first;
            first.insert(stones[0]);
            result[0] = first;
            set<int> second;
            second.insert(stones[1]);
            result[1] = second;
            int maxReach = 3;
            int maxJumpUnit = 2;
            bool canReach = false;
            for(vector<int>::size_type n = 2; n < stones.size(); ++n){
                if(stones[n] > maxReach)
                    return false;
                for(map<int, set<int> >::size_type i = 1; i <= maxJumpUnit; ++i){
                    int prevStonePos = stones[n] - i;
                    map<int, set<int> >::iterator prevStoneIndex = result.find(i-1);
                    if((prevStoneIndex != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())
                        ||((prevStoneIndex = result.find(i)) != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())
                        ||((prevStoneIndex = result.find(i+1)) != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())){
                            if(n == stones.size() - 1){
                                return true;
                            }
                            result[i].insert(stones[n]);
                            int nowCanReach = stones[n] + i + 1;
                            if(nowCanReach > maxReach)
                                maxReach = nowCanReach;
                            int nowJump = i+1;
                            if(nowJump > maxJumpUnit)
                                maxJumpUnit = nowJump;
                    }
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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