PTA Saving James Bond - Hard Version 测试点四无法通过

Question

 基本思路：

用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;
} 
​

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答

本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。

​​​​因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。