我们维护青蛙从某个石头上可以跳那些长度的距离即可 用平衡树维护。
总的复杂度O（n^2logn）
class Solution {
public:
bool canCross(vector<int>& stones) {
map<int,int>po;
int n=stones.size();
map<int,int>dis[1500];
for(int i=0;i<stones.size();i++)
po[stones[i]]=i;
dis[0][1]=1;
if(stones[1]!=stones[0]+1)return false;
dis[1][1]=dis[1][2]=1;
for(int i=1;i<stones.size();i++)
{
dis[i-1].clear();
map<int,int>::iterator it;
for(it=dis[i].begin();it!=dis[i].end();it++)
{
if(it->first<=0)continue;
int np=stones[i]+it->first;
if(po.count(np))
{
if(it->first>1)dis[po[np]][it->first-1]=1;
dis[po[np]][it->first]=1;
if(it->first<=n)dis[po[np]][it->first+1]=1;
}
}
}
if(dis[n-1].size()>0)return true;
else return false;
}
};