題意
給定一個石頭的序列，青蛙從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; }};
