403. Frog Jump

class Solution {
public:
    bool check(unordered_map<int, bool>& exist, unordered_map<int, unordered_map<int, bool>> &inq, int lastStone, int nextStone, int jumpUnits) {
        if(inq[nextStone][jumpUnits]) return false;
        if(nextStone > lastStone) return false;
        if(!exist[nextStone]) return false;
        return true;
    }
    
    bool canCross(vector<int>& stones) {
        if(stones == (vector<int>){0,1}) {
            return true;
        }
        int n = stones.size();
        if(stones.back() > (n * (1 + n - 1) / 2)) {
            return false;
        }
        unordered_map<int, bool> exist;
        for(int i : stones) exist[i] = true;
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q;
        unordered_map<int, unordered_map<int, bool>> inq;
        if(stones[1] != 1) {
            return false;
        }
        q.push(pair(1, 1));

        while(!q.empty()) {
            auto t = q.top(); q.pop();

            int nx = t.first + t.second;
            if(nx == stones.back()) return true;
            if(check(exist, inq, stones.back(), nx, t.second)) inq[nx][t.second] = true, q.push(pair(nx, t.second));

            nx = t.first + t.second + 1;
            if(nx == stones.back()) return true;
            if(check(exist, inq, stones.back(), nx, t.second+1)) inq[nx][t.second+1] = true, q.push(pair(nx, t.second+1));

            if(t.second != 1) {
                nx = t.first + t.second - 1;
                if(nx == stones.back()) return true;
                if(check(exist, inq, stones.back(), nx, t.second-1)) inq[nx][t.second - 1] = true, q.push(pair(nx, t.second -1));
            }
        }
        return false;
    }
};