A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog’s last jump was k units, then its next jump must be either k – 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
思路：这个题目可以看作是动态规划。青蛙的一个状态可以表示为{当前的k，当前的位置(可以用stone的索引表示)}，最初的时候状态就是{ 1, 0 }。在某一个状态下，青蛙可以尝试向前移动{k-1, k, k+1}步，如果能成功跳到那就进入了下一个状态。要注意的是这种状态的遍历是有重复的，所以需要一个东西记录已经尝试过（当然是尝试失败的，不然直接return true)的状态们，不然很容易超时。
为了避免栈溢出，下文的解法直接用stack模拟函数的栈调用。
class Solution {
public:
bool canCross(vector<int>& stones) {
if (stones.empty())
return false;
else if (stones.size() == 1)
return true;
// state { k, index, has_traversed }
stack<tuple<int, int, bool>> states;
unordered_map<int, set<int>> visited;
states.push({ 1, 0, false });
while (!states.empty())
{
if (std::get<2>(states.top()) == true)
{
// pop state (like recursive function returning)
states.pop();
continue;
}
int last_k = std::get<0>(states.top());
int last_pos_idx = std::get<1>(states.top());
if (visited[last_k].count(last_pos_idx) > 0)
{
// avoid duplicated state entry
states.pop();
continue;
}
std::get<2>(states.top()) = true;
visited[last_k].insert(last_pos_idx);
if (last_pos_idx == stones.size() - 1)
return true;
for (int step = last_k - 1; step <= last_k + 1; ++step)
{
if (step == 0) continue;
if (last_pos_idx == 0 && step != 1) continue; // can only move 1 step at the beginning
int next_stone = stones[last_pos_idx] + step;
for (int j = last_pos_idx + 1; j < stones.size(); ++j)
{
if (stones[j] > next_stone) break;
if (stones[j] == next_stone)
{
states.push({ step, j , false}); //Push state of the next stone
}
}
}
}
return false;
}
};
