# O(n^2) solution with detailed comments, using BFS

• ``````class Solution {
public:
using SET = unordered_set<int>;

void updateJump(unordered_map<int, SET> &s, int unit, int k) {
if (k > 0) {
const int next_unit = unit + k;
auto it = s.find(next_unit);
if (it != s.end()) {
it->second.insert(k);
}
}
}

bool canCross(vector<int>& stones) {
if (stones.empty()) {
return true;
}
// Stores all possible last-jumps for stone unit at a specific position.
unordered_map<int, SET> stones_to_jump = {{0, {0}}};
for (const int unit : stones) {
if (unit > 0) {
// Pre insert all stone unit into the map, this can
// facilitate a little.
stones_to_jump[unit] = {};
}
}
// This points to all possible last-jumps for the last stone unit.
auto final_iter = stones_to_jump.find(stones.back());
for (const int unit : stones) {
auto it = stones_to_jump.find(unit);
if (it->second.empty()) {
// If empty, then means no possible jumps to stone at <unit>
continue;
}
for (const int jump : it->second) {
// Update all other jumps starting from <unit>.
updateJump(stones_to_jump, unit, jump - 1);
updateJump(stones_to_jump, unit, jump);
updateJump(stones_to_jump, unit, jump + 1);
}
if (!final_iter->second.empty()) {
// This means we already find one solution, directly return.
return true;
}
}
return !final_iter->second.empty();
}
};
``````

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