# c++ DFS using memo

• ``````class Solution {
public:
bool canCross(vector<int> &stones) {
unordered_map<int, unordered_map<int, bool>> dir;
return helper(stones, 0, 0, dir);
}
bool helper(vector<int> &stones, int start, int k,
unordered_map<int, unordered_map<int, bool>> &dir) {
if (start == stones.size() - 1) {
return true;
}
if (dir.count(start) && dir[start].count(k)) {
return dir[start][k];
}
for (int step = max(k - 1, 1); step <= k + 1; step++) {
for (int i = start + 1; i < stones.size(); i++) {
if (stones[start] + step == stones[i] &&
helper(stones, i, step, dir)) {
dir[start][k] = true;
return true;
}
}
}
dir[start][k] = false;
return false;
}
};
``````

• another solution modified from https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations?page=1
Here is the the solution of c++

``````class Solution {
public:
bool canCross(vector<int> &stones) {
unordered_map<int, unordered_set<int>> dir;
for (auto stone : stones) {
dir[stone] = unordered_set<int>{};
}
dir[0].insert(1);
for (int i = 0; i < stones.size(); i++) {
for (int step : dir[stones[i]]) {
int reach = step + stones[i];
if (reach == stones[stones.size() - 1]) {
return true;
}
if (dir.count(reach)) {
for (int j = max(step - 1, 1); j <= step + 1; j++) {
dir[reach].insert(j);
}
}
}
}
return false;
}
};
``````

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