Description

Submission

class Solution {
    set<pair<int,int>> failed;
    unordered_set<int> stonesSet;
    
public:
    bool canCross(vector<int>& stones) {
        for(auto stone: stones) {
            stonesSet.insert(stone);
        }

        return dfs(stones, 0, 0);
    }

    bool dfs(vector<int>& stones, int pos, int jump) {
        if(pos == stones.back()) return true;
        if(stonesSet.find(pos) == stonesSet.end()) return false;
        if(failed.find({pos, jump}) != failed.end()) return false;

        int curPos = pos + jump;
        if(jump-1 > 0 && dfs(stones, curPos, jump - 1)) return true;
        if(jump > 0 && dfs(stones, curPos, jump)) return true;
        if(dfs(stones, curPos, jump + 1)) return true;
        failed.insert({pos, jump});
        return false;
    }
};