07-图5 Saving James Bond - Hard Version（困难版）

71 阅读 0 评论 47 点赞

我是靠谱客的博主开心方盒，最近开发中收集的这篇文章主要介绍07-图5 Saving James Bond - Hard Version（困难版），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.
这一次让我们考虑一下电影“生活和让死”中的情况，其中詹姆斯邦德是世界上最着名的间谍，被一群毒贩抓获。他被送到一个充满鳄鱼的湖中心的一小块土地上。他在那里表演了最大胆的逃跑行动 - 他跳到最近的鳄鱼头上！在动物意识到发生了什么事之前，詹姆斯再次跳到下一个大头上…最后他到达了银行，最后一条鳄鱼咬了他（实际上这个特技演员被大嘴抓住，几乎没有用他的特厚靴子逃脱）。

假设湖面是100乘100平方。假设湖的中心位于（0,0），东北角位于（50,50）。中央岛是一个以（0,0）为中心的圆盘，直径为15.许多鳄鱼都在湖中的不同位置。考虑到每只鳄鱼的坐标和詹姆斯可以跳跃的距离，你必须告诉他到达其中一条河岸的最短路径。路径的长度是詹姆斯必须进行的跳跃次数。

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.
每个输入文件包含一个测试用例。每个案例都以包含两个正整数的行开头N（≤ 1 0 0），鳄鱼的数量，和D，詹姆斯可以跳的最大距离。然后接下来是N行，每行包含（x ，y ）鳄鱼的位置。请注意，没有两条鳄鱼停留在同一位置。

Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.
对于每个测试用例，如果詹姆斯可以逃脱，则在一行中输出他必须进行的最小跳跃次数。然后从下一行开始输出位置（x ，y ）每条鳄鱼在路径上，每一对都在一条线上，从岛屿到岸边。如果詹姆斯不可能以这种方式逃脱，那就简单地给他0作为跳跃的数量。如果有许多最短路径，只需输出具有最小第一跳的路径，这保证是唯一的。

Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10
Sample Output 1:
4
0 11
10 21
10 35

Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
0

代码讲解（与Saving James Bond - Easy Version（拯救詹姆斯邦德）类似，点即可了解

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Maxsize 1000
struct GraphNode{
	int topnum;
	int Maxdistance;
	int G[Maxsize][Maxsize];
};
struct Node{
	int v1;//起始点
	int v2; //末点
	int prenum;//前面一个顶点编号
//	int nownum;//自生编号
}zuobiao[Maxsize];
typedef struct GraphNode *GRAPH;
int Distance(int x,int y,GRAPH graphptr)
{
	return ( graphptr->Maxdistance * graphptr->Maxdistance >= (zuobiao[x].v1 - zuobiao[y].v1 ) * (zuobiao[x].v1 - zuobiao[y].v1 ) + (zuobiao[x].v2 - zuobiao[y].v2 ) * (zuobiao[x].v2 - zuobiao[y].v2 ));
}
void ComputeRightDis(GRAPH graphptr)
{
	int i = 0,j = 0;
	int dis = 0;
	for(i = 0;i <= graphptr->topnum - 1;i++)
	{
		for(j = 0;j <= graphptr->topnum - 1;j++)
		{
			dis = Distance( i , j ,graphptr);
			if( dis == 1 )//跳的距离判断是否在范围内
			{
				graphptr->G[ i ][ j ] = 1;
				graphptr->G[ j ][ i ] = 1;
			}
		}
	}
}
int Issafe(int v,GRAPH graphptr)
{
	return zuobiao[v].v1 <= -( 50 - graphptr->Maxdistance) || zuobiao[v].v1 >= 50 - graphptr->Maxdistance || zuobiao[v].v2 <= -( 50 - graphptr->Maxdistance) || zuobiao[v].v2  >=  50 - graphptr->Maxdistance;
}
int BFS(GRAPH graphptr)
{
	int i = -1,j = 0;
	while( ++i >= 0 && i <= graphptr->topnum - 1)
	{
		if(((graphptr->Maxdistance+7.5)*(graphptr->Maxdistance+7.5)>=(zuobiao[i].v1*zuobiao[i].v1 + zuobiao[i].v2*zuobiao[i].v2))&& (zuobiao[i].v1 *4* zuobiao[i].v1 + zuobiao[i].v2 *4* zuobiao[i].v2 > 225 )&& abs(zuobiao[i].v1) <=50 && abs(zuobiao[i].v2 <= 50))//第一批临近点)
		{
			int visited[Maxsize];
			int Queue[Maxsize];
			int front = -1;
			int rear = -1;
			Queue[++rear] = i;
			visited[i] = 1;
			zuobiao[i].prenum = -1;
			while(front != rear)
			{
				i = Queue[++front];//出队
				if( Issafe( i , graphptr ))//判断是否可以上岸
					return i;
				for(j = 0;j <= graphptr->topnum - 1;j++)
				{
					if(visited[j] == 0 && graphptr->G[i][j] == 1 && (zuobiao[j].v1 *4* zuobiao[j].v1 + zuobiao[j].v2 *4* zuobiao[j].v2 > 225 ))//与 v 相连的点
					{
						visited[j] = 1;
						Queue[++rear] = j;
						zuobiao[j].prenum = i;
					}
				}
			}
		}
	}
	return 0;
}
int main()
{
	int N = 0,D = 0,i = 0,j = 0,visited[Maxsize];
	scanf("%d %d",&N,&D);
        if( D+7.5 >= 50)
        {
		printf("1n");
	}
	else
	{
		GRAPH graphptr = (GRAPH)malloc(sizeof(struct GraphNode));
		graphptr->topnum = N;
		graphptr->Maxdistance = D;
		for(i = 0;i <= graphptr->topnum - 1;i++)
		{
			scanf("%d %d",&zuobiao[i].v1,&zuobiao[i].v2);
		}
		ComputeRightDis(graphptr);//计算满足要求的点的距离
		int answer = BFS( graphptr );
		if(answer == 0)
			printf("0n");
		else
		{
			int stack[100], top = 0,pace = 1,v = answer;  //栈
			while (v != -1)
			{                     //回溯路径，依次压栈
				++pace;
				stack[top++] = v;
				v = zuobiao[v].prenum;
			}
			printf("%dn", pace);//总次数
			while (top)
			{                   //依次弹出栈内元素
				v = stack[--top];
				printf("%d %dn",zuobiao[v].v1,zuobiao[v].v2);
   			}
		}
	}
	return 0;
}