Frogger
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 23230 | Accepted: 7550 |
Description
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input
2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
题意:
给出 N(2 ~ 200),说明有 N 块石头,后给出每块石头 x,y (0 ~ 1000)坐标。第一块石头代表起点坐标,第二块石头代表终点坐标。求从起点到达终点的所有路径中,直接相连最小的距离范围。
比如1到2有两条路,分别为1 -> 2距离为2,故这条路的直接相连所需最大范围为2;
还有一条为1 -> 3 -> 2 距离分别为根号2 和根号2,故这条路直接相连所需最大范围为根号2;
因为2 < 根号2,故最小距离范围为2。
思路:
本质是最短路。题目略有点难理解。每个节点保存当前的最大所需范围,若每次更新新的最大所需范围比当前小,则更新这个最大所需范围的值。Dijkstra + 邻接表 + 优先队列。用 double 型保存距离,输出的时候注意输出最后三位即可。
AC:
#include <cstdio> #include <queue> #include <vector> #include <utility> #include <math.h> #include <string.h> #include <algorithm> #define MAX 50000 #define INF 99999999 using namespace std; typedef pair<double,int> pii; typedef struct { double x,y; }node; node no[205]; int v[MAX],next[MAX],fir[205],vis[205]; double w[MAX],d[205]; int ind,n; double Distance(node a,node b) { double x = a.x - b.x; double y = a.y - b.y; return sqrt(x * x + y * y); } void add_edge(int f,int t,double val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ind++; } void Dijkstra() { memset(vis,0,sizeof(vis)); for(int i = 1;i <= n;i++) d[i] = INF; priority_queue<pii,vector<pii>,greater<pii> > q; d[1] = 0; q.push(make_pair(d[1],1)); while(!q.empty()) { pii k = q.top();q.pop(); int x = k.second; if(vis[x]) continue; vis[x] = 1; for(int e = fir[x];e != -1;e = next[e]) { int y = v[e]; double max_ran = max(w[e],d[x]); if(d[y] > max_ran) { d[y] = max_ran; q.push(make_pair(d[y],y)); } } } } int main() { int t = 0; while(~scanf("%d",&n) && n) { t++; ind = 0; memset(fir,-1,sizeof(fir)); for(int i = 1;i <= n;i++) scanf("%lf%lf",&no[i].x,&no[i].y); for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) { if(i == j) continue; double s = Distance(no[i],no[j]); add_edge(i,j,s); } Dijkstra(); printf("Scenario #%d\n",t); printf("Frog Distance = %.3lf\n\n",d[2]); } return 0; }
相关推荐
Frogger+ Extreme 使用 GDI+ 在 VB .NET 中重新创建。 非常基本但非常新。
pku acm 2253 Frogger 代码 单元最短路径 Dijkstra算法
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
Frogger(Furoggā的Frogger)是Konami于1981年开发的街机游戏,最初由Sega发行。[2] 在北美,它由Sega和Gremlin Industries联合出版。 游戏的目的是通过穿越繁忙的马路并在充满危险的河流中将青蛙一个个地引导到...
蛙人 这是用Java创建的简单Frogger克隆。 有一些错误。
Udacity前端Web开发人员纳米学位项目3 该项目的目标:重新创建我自己版本的蛙人街机游戏。... 用于创建游戏的资源:Udacity课程:面向对象的Javascript HTML5 Canvas Frogger游戏-入门google doc: :
使用Java Swing库开发的简单Frogger游戏。 GUI和引擎位于单独的文件中。 怎么玩: 播放器控制屏幕底部的青蛙。 目标是在屏幕的另一侧到达目标,避开汽车和树林。 控制项: 向上-将青蛙向上移动一个单位 左-将青蛙...
青蛙:HTML5 版本Frogger 是一款简单的游戏,玩家试图穿越地图避免与敌人发生碰撞。 敌人随机放置在地图开头(左侧)的不同位置,并从左向右移动。 玩家可以使用键盘箭头上下、左右移动。 一旦玩家到达最后一排,就...
蛙人Java的Frogger游戏
青蛙游戏 这个游戏本质上是让玩家在不与任何敌怪碰撞的情况下到达水块。 玩家可以向左、向右、向上和向下移动。 每当玩家与虫子碰撞时,玩家都会返回其初始位置。 当玩家到达水块时,它也会返回到其初始位置。
Frogger-Udacity前端纳米度的一部分使用面向对象的Javascipt构建的经典街机游戏。 我建立了这个游戏来练习编写面向对象的javascript。 app.js,css和html是我自己的代码,而resources.js和engine.js(除了一些调整)...
这个想法是重新创建经典的Frogger街机游戏的简单副本。怎么玩单击此链接玩游戏: *************************** 使用箭头键将您的播放器移动到臭虫出没的道路上,并确保“蓝色臭虫免费”部门的安全。 每次成功过关得...
Frogger-MobileApp
要做的工作今年计算机图形实验室的工作目的是使用C和++ OpenGL重新创建此经典版本的3D版本。 这个想法是保持原始游戏玩法改变图形视角,以便游戏的各个元素具有一个3D方面。 您可以在下面的图中看到一个启发示例。...
java swing简单源码蛙跳 一个简单的基于Java swing的游戏。 与Frogger类似。 v1.0 -需要更好的文档
入门:要开始下载游戏或在本地计算机上克隆此存储库。... 玩法:您只需要使用箭头键即可移动角色。 游戏目标:游戏的目标是在避免虫子的情况下入水! 如果您被虫子吞噬了,请放心,您将获得另一个机会!...
FrogLord-Frogger改装工具什么是FrogLord? FrogLord是Frogger(1997)的改装套件。 它允许粉丝创建新关卡,导入3D模型,查看未使用的内容并允许更改所有游戏文件。 要使用此工具,您必须拥有游戏的副本。屏幕截图:...
这是我第一次编程游戏! 这是一个原型独特的蛙人,这是关于蛙人家庭的一切,而你就是the头。 那去拿钱吧! 冒着生命危险,穿越宽阔的街道和广阔的海洋。 河。 是的。 没什么大不了。... 详细信息:用Slick2D和LWJGL用...
在每个新选项卡上玩经典的街机游戏Frogger。 躲避汽车,不要掉入水中! 包括睡莲叶背景。 每次打开新的标签页时,您就可以测试您的技能并玩经典的街机游戏Frogger! 目的是在不被汽车撞到或掉入水中的情况下直达河的...
Frogger-Controller-Android 可以将 Frogger 控件传输到服务器的应用程序。 抓住APK,并用它玩游戏!