C++ DFS + memory 33 ms

• ``````class Solution {
public:
bool canCross(vector<int>& stones) {
if (stones.size() < 2) {
return false;
}

int des = stones.back();
unordered_map<int, unordered_set<int>> memo;
//          start  steps
unordered_set<int> stones_set(stones.begin(), stones.end());
return dfs(stones_set, 0, 1, des, memo);
}
private:
bool dfs(unordered_set<int> &stones, int start, int step, const int &des, unordered_map<int, unordered_set<int>> &memo) {
if (memo.find(start) != memo.end() && memo[start].find(step) != memo[start].end()) {
return false;
}
int next = start + step;
if (next == des) {
return true;
}
if (stones.find(next) == stones.end()) {
memo[start].insert(step);
return false;
}

if (dfs(stones, next, step + 1, des, memo) ||
dfs(stones, next, step, des, memo) ||
(step > 1 && dfs(stones, next, step - 1, des, memo))) {
return true;
}
memo[start].insert(step);
return false;
}
};
``````

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