Leetcode 403 - Frog Jump（dp or bfs）

题意

给定一个石头的序列，青蛙从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_pair class 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 2 class 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; } };