本文主要是介绍POJ2253 Frogger 【Floyd】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
讲的是，一只雄青蛙要从一个石头到另外一个石头上去找某只雌青蛙，但是这两个石头隔得太远，青蛙跳不过去，所幸，湖面上还有很多其他石头，所以青蛙可以借助别的石头一步一步地跳向那只雌青蛙所在的石头。显然青蛙可能有多种路径，比如其中一条是 2，3，4，2，1 ，它跳了五次，数字代表每次跳的距离也就是路径上相邻两个石头之间的距离，那么这只青蛙的弹跳能力至少是4才能跳过去。在其他的路径中，可能要求青蛙的弹跳是5，是8，是1，是100，等等，这个问题求青蛙需要的最小弹跳能力。其实也就是个最大值中取最小的问题。
直接求较为困难，我们试着用floyd算法来做这道题。Floyd算法非常好懂，两个结点，i,j，中间结点k枚举所有点，如果从i->k->j比较优，更新path[i][j]的值。
这里i->k->j比较优的情况就是i到j的距离比i到k和k到j都大，更新的值是i->k和k->j两者中的较大者（显然，要保证足够的弹跳能力）
path[i][j]的含义也就是i到j所需要的最小弹跳能力
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
struct point
{int x,y;
}p[222];
double path[222][222];
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifint casenum=0;while(true){memset(p,0,sizeof(p));memset(path,0,sizeof(path));int stonenum;cin>>stonenum;if(!stonenum)break;casenum++;for(int i=1;i<=stonenum;i++)cin>>p[i].x>>p[i].y;for(int i=1;i<=stonenum-1;i++){for(int j=i+1;j<=stonenum;j++){path[j][i]=path[i][j]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));}}for(int k=1;k<=stonenum;k++){for(int i=1;i<=stonenum-1;i++){for(int j=i+1;j<=stonenum;j++){if(path[i][j]>path[i][k]&&path[i][j]>path[k][j]){path[i][j]=path[j][i]=max(path[i][k],path[k][j]);}}}}printf("Scenario #%d\n",casenum);printf("Frog Distance = %.3f\n\n",path[1][2]);}
}
这篇关于POJ2253 Frogger 【Floyd】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
