Problem 534 Frogger，蛙跳的最小距離

此題給你一些石頭的座標，而要從第一顆石頭跳到第二顆石頭所用最小距離是多少 ( 注意：是最小，不是最短 )。舉個例子，就拿第二個輸入範例來說，
3
17 4 <- 第一顆石頭 ( Freddy所在之石 )
19 4 <- 第二顆石頭 ( Fiona所在之石 )
18 5 <- 第三顆石頭

我們可以簡略算出 1 <--> 2 距離為 2，2 <--> 3 距離為 1.41421，3 <--> 1 距離為 1.41421。如果以最短路徑來說，從 1 直接跳到 2 最快。但以最小距離來說，從 1 跳到 3 再跳到 2，所用只要用 1.41421 的距離便可跳到 2，若直接從 1 跳到 2，便會花上 2.0 距離之長。這就不符合我們所說的最小距離。

一開始我們先將所有石頭之間的距離放入陣列，再用「最小路徑演算法」便可求出最小距離，C 語言程式碼如下：

for (i = 0; i < n; i ++)
    scanf("%f %f", &pt[i][0], &pt[i][1]);
for (i = 0; i < n; i ++)
{
    W[i][i] = 0;
    for (j = i + 1; j < n; j ++)
    {
        W[i][j] = sqrt( (pt[i][0] - pt[j][0]) * (pt[i][0] - pt[j][0]) + 
                        (pt[i][1] - pt[j][1]) * (pt[i][1] - pt[j][1]) );
        W[j][i] = W[i][j];               
    }
}
for (k = 0; k < n; k ++)
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
        {
            W[i][j] = min(W[i][j], max(W[i][k] , W[k][j]));
        }
printf("Scenario #%d\n", caseNum ++);        
printf("Frog Distance = %.3f\n\n", W[0][1]);

By David.K

p534題目連結
回ACM題庫目錄
回首頁