题意
给定一个石头的序列，青蛙从0开始跳，第一次只能跳一步，不能落入水中。
现在，假如我从上一个石头跳到这个石头是k步，那么，我们下一次只能跳k - 1或k或k + 1步，问：青蛙最后能否调到最后一个石头上。
思路
算法1
爆搜，本来以为会T，但是实际上中间会有很多情况会落入水中，所以bfs能过。
算法2
dp，我们可以这样考虑：我们当前在位置i，是从位置j经过k步到达位置i的。那么我们下一次能够达到stonesi+k或stonesi+k−1或stonesi+k+1。
于是，我们的状态表示为：d[i]，从i之前的某一位置j经过k步跳过来的，那么，很明显我们的d[i]有很多种情况，我们可以再加一维j表示从j经过d[i,j]步跳过来的，也可以用一个set来存我们经过多少步到i的。
即，我们定义我们的d[i]为unordered_map<int, set<int>> pos，key为stones[i]，value为跳到这个位置的所有可能步数集合。
那么，我们接下来需要做的就是：假设我们当前在位置i，我们取出pos[stones[i]]对应的集合tk。对于tk内的每一个步数k，那么我们下一次就可以走到的位置newpos为stones[i] + k或stones[i] + k - 1或stones[i] + k + 1。然后判断newpos是否为一个石头，如果是，那么我们就将可行的解加入pos即可。
最后，只需要判断pos[stones[n - 1]].size()>0即可（即是否存在到终点的可行步数）
代码
//algorithm 1#define PII pair<int, int>#define mp make_pairclass Solution {public: bool canCross(vector<int>& stones) { set<PII> vis; set<int> has; for (auto x : stones) has.insert(x); int ll = stones[stones.size() - 1]; queue<PII> q; q.push(mp(1, 1)); while (!q.empty()) { PII t = q.front(); q.pop(); if (t.first == ll) return true; if (vis.find(t) != vis.end()) continue; else vis.insert(t); int x = t.first, k = t.second; if (has.find(x) != has.end()) { if (x + k <= ll && has.find(x + k) != has.end()) q.push(mp(x + k, k)); if (x + k - 1 <= ll && has.find(x + k - 1) != has.end()) q.push(mp(x + k - 1, k - 1)); if (x + k + 1 <= ll && has.find(x + k + 1) != has.end()) q.push(mp(x + k + 1, k + 1)); } } return false; }};//algorithm 2class Solution {public: bool canCross(vector<int>& stones) { unordered_map<int, set<int>> pos; set<int> tmp; for (auto x : stones) pos[x] = tmp; for (int i = 0; i < stones.size(); i++) { set<int> sk = pos[stones[i]]; for (auto k : sk) { for (int step = k - 1; step <= k + 1; step++) { if (step > 0 && pos[stones[i] + step] != NULL) pos[stones[i] + step].insert(stones[i] + step); } } } return pos[stones.size() - 1].size() > 0; }};
