浙大数据结构：07-图5 Saving James Bond - Hard Version

这道题也是很有难度，我最开始尝试用Dijkstra来做，发现不是很好处理，用bfs还不错。

机翻：

1、条件准备 

n为鳄鱼数量，jump为跳跃距离，headjump为第一次跳跃距离，包括了岛的半径。

isalive标识该鳄鱼是否能到达对岸。

eyu数组存每个鳄鱼的坐标

visit存该鳄鱼是否访问过

lasteyu数组标识跳到该鳄鱼的上一头鳄鱼是哪条

  #include <iostream>#include<vector>#include<string.h>#include<algorithm>#include<stack>using namespace std;#define endl '\n'int n,jump;double headjump;
int isalive[105];
pair<int,int> eyu[105];
int visit[105];
int lasteyu[105];

2、主函数

首先输入数据，headjump为跳跃距离加岛的半径。

令下标为104的鳄鱼为岛屿中心，这里我们令所有坐标都加50，当正数处理。中心就是（50，50）

dis数组是存能第一次跳到的鳄鱼。

循环输入每条鳄鱼信息，坐标都加上50然后存到eyu数组里。

如果该鳄鱼能跳到对岸，则isalive数组标记为1

判断该头鳄鱼是否能第一次跳到，能的话加到dis数组里。

这里注意，我们把鳄鱼据岛中心的距离用codis函数算出来*1000再加上鳄鱼下标i。

这样我们对该数组进行排序，就是按照离岛中心的距离来排序，因为下标的影响很小，不会影响到总体大小。

当我们要用的时候，可以对1000取模来看看是哪头鳄鱼。

注意如果能一步跳出单独判断，然后进入bfs就行了

int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>jump;vector<int> dis;headjump=jump+7.5;eyu[104].first = 50, eyu[104].second = 50;
for(int i=0;i<n;i++){int a, b;cin >> a >> b;a += 50, b += 50;eyu[i].first = a, eyu[i].second = b;if (a <= jump || 100 - a <= jump || b <= jump || 100 - b <= jump)isalive[i] = 1;if(isjump(i,104,headjump))dis.push_back(codis(i,104)*1000+i);}sort(dis.begin(),dis.end());if(jump>=42.5){cout<<'1';return 0;}bfs(dis);return 0;}

3、codis函数

算两头鳄鱼之间的距离并返回，abs是取绝对值函数

int codis(int a,int b)
{int x = abs(eyu[a].first - eyu[b].first);int y = abs(eyu[a].second - eyu[b].second);return x*x+y*y;
}

4、isjump函数

判断两头鳄鱼之间距离是否为dis

bool isjump(int a, int b, double dis)
{if ((double)codis(a,b) <= dis * dis)return 1;return 0;
}

5、bfs函数

代码比较长，我们一点点看。

minjump是存跳的鳄鱼的最少数量，answer栈是存最短路上鳄鱼下标的。

循环遍历dis数组，表示从该头鳄鱼开始跳到岸边的最短路

初始化每一头鳄鱼的上一头鳄鱼为-1，visit数组置0

cur存当前为第几头鳄鱼开始跳，对1000取模即可。

然后用数组模拟队列，tt指队尾，hh指队头

把cur放进队列中，visit置1

layer表示第几步跳到当前鳄鱼，初始为第一步（即cur)

last标记上一步的最后一头鳄鱼,初始为cur因为第一步只能为cur。

遍历队列直到为空，用now取出当前队头是第几头鳄鱼，然后循环判断它能不能跳到其它鳄鱼并且该鳄鱼没有被跳到过，有的话加入队列visit置1，然后该头鳄鱼的上一头鳄鱼为now

如果当前鳄鱼能跳到岸边，并且最短路小于mindist，则更新答案，mindist为layer，answer清空把该最短路上的鳄鱼加进来，即遍历lasteyu数组，直到该鳄鱼没有上一头鳄鱼（为-1），跳出循环。

如果不能跳到岸边，则看看是否更新步数，即当前鳄鱼为上一步所能到达的所有鳄鱼中放入队列的最后一头，更新layer，last更新为队尾。

最后遍历完输出答案，如果mindist没更新输出0，

否则输出步数（鳄鱼头数+1），然后弹出栈里的鳄鱼并输出，此时顺序刚好是对的。

void bfs(vector<int>&dis)
{int minjump=1000; stack<int> answer;//存答案for(int i=0;i<dis.size();i++){memset(lasteyu,-1,sizeof(lasteyu));memset(visit,0,sizeof(visit));int cur=dis[i]%1000;int q[105];int tt=-1,hh=0;visit[cur]=1;q[++tt]=cur;int last=cur;int layer=1;
//从每一个能第一步跳到的鳄鱼开始跳然后判断while(hh<=tt){int now=q[hh++];
//把能跳到的鳄鱼加进队列for(int j=0;j<n;j++){if(!visit[j]&&isjump(now,j,jump)){visit[j]=1;q[++tt]=j;lasteyu[j]=now;}}
//如果跳到该鳄鱼了，并且距离短就更新答案if(isalive[now]&&layer<minjump){minjump=layer;answer=stack<int>();for(;now!=-1;now=lasteyu[now])answer.push(now);break;}
//更新层数，也就是跳的次数if(now==last){last=q[tt];layer++;} }}
//输出答案if(minjump!=1000){cout<<minjump+1<<endl;while(answer.size()){int cur=answer.top();cout<<eyu[cur].first-50<<' '<<eyu[cur].second-50<<endl;answer.pop();}}else cout<<'0';
} 

6、总结

这道题难度比较大，主要很多细节不好处理，比较耗时。

完整代码如下：

  #include <iostream>#include<vector>#include<string.h>#include<algorithm>#include<stack>using namespace std;#define endl '\n'int n,jump;double headjump;
int isalive[105];
pair<int,int> eyu[105];
int visit[105];
int lasteyu[105];int codis(int a,int b)
{int x = abs(eyu[a].first - eyu[b].first);int y = abs(eyu[a].second - eyu[b].second);return x*x+y*y;
}bool isjump(int a, int b, double dis)
{if ((double)codis(a,b) <= dis * dis)return 1;return 0;
}void bfs(vector<int>&dis)
{int minjump=1000; stack<int> answer;for(int i=0;i<dis.size();i++){memset(lasteyu,-1,sizeof(lasteyu));memset(visit,0,sizeof(visit));int cur=dis[i]%1000;int q[105];int tt=-1,hh=0;visit[cur]=1;q[++tt]=cur;int last=cur;int layer=1;while(hh<=tt){int now=q[hh++];for(int j=0;j<n;j++){if(!visit[j]&&isjump(now,j,jump)){visit[j]=1;q[++tt]=j;lasteyu[j]=now;}}if(isalive[now]&&layer<minjump){minjump=layer;answer=stack<int>();for(;now!=-1;now=lasteyu[now])answer.push(now);break;}if(now==last){last=q[tt];layer++;} }}if(minjump!=1000){cout<<minjump+1<<endl;while(answer.size()){int cur=answer.top();cout<<eyu[cur].first-50<<' '<<eyu[cur].second-50<<endl;answer.pop();}}else cout<<'0';
} int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>jump;vector<int> dis;headjump=jump+7.5;eyu[104].first = 50, eyu[104].second = 50;
for(int i=0;i<n;i++){int a, b;cin >> a >> b;a += 50, b += 50;eyu[i].first = a, eyu[i].second = b;if (a <= jump || 100 - a <= jump || b <= jump || 100 - b <= jump)isalive[i] = 1;if(isjump(i,104,headjump))dis.push_back(codis(i,104)*1000+i);}sort(dis.begin(),dis.end());if(jump>=42.5){cout<<'1';return 0;}bfs(dis);return 0;}