基本思路：
用Floyd算法，将任意两条鳄鱼之间的距离表示在邻接矩阵中。找出所有第一步就可以跳上去的鳄鱼并将编号储存在first_jump数组中，再找出只要跳一步就能上岸的鳄鱼并将编号储存在last_jump数组中。找出从first_jump到last_jump中距离最短的，再加2(第一步从湖中心跳到第一条鳄鱼以及最后一步从鳄鱼跳到岸上)。对于路径的回溯，只需要利用path递归输出即可。
特殊情况处理：
如果直接一步就能跳上岸，则直接输出"0"；
如果存在一条鳄鱼，它既属于first_jump又属于last_jump，就直接输出跳跃步数"2"，然后输出该鳄鱼的位置;(因为从自己到自己的跳跃步数是INFINITY，在一般情况不会被正确处理)
该方法存在哪些问题？
#include<iostream>
#include<math.h>
#define INFINITY 65536
#define MaxVertexNum 100
using namespace std;
int Graph[MaxVertexNum][MaxVertexNum];//所有鳄鱼默认从0开始编号
int path[MaxVertexNum][MaxVertexNum];//存储路径
struct Location {
int X;
int Y;
};
void Floyd(int Nv) {
int k, i, j;
for (int i = 0; i < Nv; i++)
for (int j = 0; j < Nv; j++)
path[i][j] = -1;
for (k = 0; k < Nv; k++)
for (i = 0; i < Nv; i++)
for (j = 0; j < Nv; j++)
if (Graph[i][k] + Graph[k][j] < Graph[i][j]) {
Graph[i][j] = Graph[i][k] + Graph[k][j];
path[i][j] = k;
}
}
void print(int i, int j,Location* save) {
if (j==-1) {
cout << save[i].X << " " << save[i].Y << endl;
return;
}
print(i, path[i][j], save);
cout << save[j].X << " " << save[j].Y << endl;
}
int main() {
int Nv, D;
cin >> Nv >> D;
if (7.5 + D >= 50) {
cout << "1";
return 0;
}
Location* save_all_locations = new Location[Nv];
int x, y;
for (int i = 0; i < Nv; i++) {//所有鳄鱼坐标信息
cin >> x >> y;
save_all_locations[i].X = x;
save_all_locations[i].Y = y;
}
for (int i = 0; i < Nv; i++) {//初始化所有鳄鱼之间的边的信息
for (int j = 0; j < Nv; j++) {
if (i == j)
Graph[i][j] = INFINITY;
else {
int X_i = save_all_locations[i].X;
int Y_i = save_all_locations[i].Y;
int X_j = save_all_locations[j].X;
int Y_j = save_all_locations[j].Y;
if ((X_i - X_j) * (X_i - X_j) + (Y_i - Y_j) * (Y_i - Y_j) <= D * D) {
Graph[i][j] = 1;
Graph[j][i] = 1;
}
else {
Graph[i][j] = INFINITY;
Graph[j][i] = INFINITY;
}
}
}
}
//找出所有可以第一下就跳上去的鳄鱼,并储存其编号(数组顺序储存)
int* first_jump = new int[Nv];
int count1=0;
for (int i = 0; i < Nv; i++)
first_jump[i] = 0;
for (int i = 0; i < Nv; i++)
if (save_all_locations[i].X * save_all_locations[i].X + save_all_locations[i].Y * save_all_locations[i].Y <= (7.5 + D) * (7.5 + D))
first_jump[count1++] = i;//储存编号i
//找出所有可以跳到岸上的鳄鱼，并储存其编号(数组顺序储存)
int* last_jump = new int[Nv];
int count2 = 0;
for (int i = 0; i < Nv; i++)
last_jump[i] = 0;
for (int i = 0; i < Nv; i++)
if (50 - fabs(save_all_locations[i].X) <= D || 50 - fabs(save_all_locations[i].Y) <= D)
last_jump[count2++] = i;
Floyd(Nv);//求出任意两条鳄鱼之间的跳跃步数
int min_jump = INFINITY;
int first, last;
int temp;
if (count1 == 0 || count2 == 0) {
cout << "0";
return 0;
}
else {
for (int i = 0; i < count1; i++) {
for (int j = 0; j < count2; j++) {
if (first_jump[i] == last_jump[j]) {//如果first同时也是last，直接输出
cout << "2" << endl;
cout << save_all_locations[first_jump[i]].X << " " << save_all_locations[first_jump[i]].Y;
return 0;
}
temp = Graph[first_jump[i]][last_jump[j]];
if (temp != INFINITY && temp < min_jump) {
min_jump = temp;
first = first_jump[i];
last = last_jump[j];
}
}
}
}
if (min_jump == INFINITY)
cout << "0";
else {
int min_num=0;
for (int i = 0; i < count2; i++)
if (Graph[first][last_jump[i]] == min_jump)
min_num++;
cout << min_jump + 2 << endl;
if (min_num == 1)
print(first, last, save_all_locations);
else
cout << save_all_locations[first].X << " " << save_all_locations[first].Y;
}
return 0;
}
你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答
本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。
因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。