Floyed算法[通俗易懂]

Floyed算法[通俗易懂]这一讲简单介绍一下Floyed算法。话不多说,先放一道题帮助理解(其实是懒得描述具体应用场景)。FroggerFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisit

大家好,又见面了,我是你们的朋友全栈君。

这一讲简单介绍一下Floyed算法。
话不多说,先放一道题帮助理解(其实是懒得描述具体应用场景)。
Frogger

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.

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

严格来说,这并不是一道标准的Floyed题,题意是:在所有通路中,找到每一条通路中的最大距离,在这所有的距离中,找到一个最小值。
之所以也放到这里,首先是因为Floyed算法标志性的三重循环,其次也是想借此拓展一下该算法灵活的应用方式


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define maxsize 1010
#define inf 99999999
int x[maxsize],y[maxsize],sum=1;
double dis[maxsize][maxsize];//用来记录任意两点通路的单步最大长度

//计算两点间的距离
double caldistance(int x1,int y1,int x2,int y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
    int m;
    while(scanf("%d",&m)!=EOF)
    {
        if(m==0)
        {
            break;
        }
        int i,j,k;

        //输入每个点的坐标
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&x[i],&y[i]);
        }

        //计算任意两个点间的距离
        for(i=1;i<=m;i++)
        {
            for(j=i;j<=m;j++)
            {
                if(j==i) dis[i][j]=0;
                else
                dis[i][j]=dis[j][i]=caldistance(x[i],y[i],x[j],y[j]);
            }
        }
        //算法标志性的三重循环
        //特别暴力的找到所有情况然后更新
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=m;j++)
            {
                for(k=1;k<=m;k++)
                {
                    if(dis[j][k]>max(dis[j][i],dis[i][k]))
                    {
                        dis[j][k]=max(dis[j][i],dis[i][k]);
                        //注意i,j,k的顺序和位置,最初写错了,怎么都找不到问题错在哪里,一定要注意,
                        //如果是找最短路径的正宗Floyed,比较的就是dis[j][k]和dis[j][i]+dis[i][k]的大小,取小的那个
                    }

                }
            }
        }

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", sum++, dis[1][2]);
    }
    return 0;
}

这个题巧妙的一点改动就实现了功能的“巨大”改变。

算法的核心就是那个三重循环及其嵌套顺序。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/147969.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vue JS 对象转数组[通俗易懂]

    vue JS 对象转数组[通俗易懂]option:{ head:{ title:”日期”, name:date, width:180 }, data:{ date:”2021-05-27″, name:”张三”, address:”上海市浦东新区XX路XX号” } }转数组:letoption=this.option;letArr=Object.keys(option).map(k

  • 【深度学习】【语义分割】ASPP

    【深度学习】【语义分割】ASPPASPP空洞空间卷积池化金字塔(atrousspatialpyramidpooling(ASPP))对所给定的输入以不同采样率的空洞卷积并行采样,相当于以多个比例捕捉图像的上下文。上图为deeplabv2的ASPP模块,deeplabv3中向ASPP中添加了BN层,其中空洞卷积的rate的意思是在普通卷积的基础上,相邻权重之间的间隔为rate-1,普通卷积的rate默认为1,所以…

  • ceph常用命令详解_ceph osd

    ceph常用命令详解_ceph osd1.OSD概念OSD:ObjectStorageDevice,主要负责响应客户端请求返回具体数据的守护进程,一般一个集群会有多个OSD,每一块盘都会对应一个OSD。2.OSD状态[root@data1~]#cephosdstat4osds:3up(since23m),3in(since13m);epoch:e345OSD状态说明:a.集群内(in)b.集群外(out)c.活着且在运行(up)d.挂了且不再运行(down).

    2022年10月29日
  • mac上传文件到aws ec2 instance「建议收藏」

    mac上传文件到aws ec2 instance「建议收藏」mac上使用ec2实例确实比较简洁:使用scp上传文件到ec2instance上:1.在ec2instance上创建上传文件目录mkdir/home/upload2.调整目录权限,用于上传使用chmod0777/home/upload这里必须调整为777权限,否则上传用户无法写入3.在本地上传文件至ec2instance

  • eplan激活码分享-激活码分享

    (eplan激活码分享)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSWQi…

  • IIS浏览提示无法显示网页的解决方法

    IIS浏览提示无法显示网页的解决方法

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号