c125 - 00534 - Frogger
題目描述
題目描述了青蛙 Freddy 想要跳到 Fiona 的石頭上，但直接跳躍距離過遠。因此，Freddy 必須利用湖中的其他石頭作為中繼站。題目要求計算蛙跳距離，即 Freddy 從起始石頭跳到 Fiona 石頭的路徑中，所需的最大跳躍距離的最小值。
解題思路
本題可以建模為一個圖論問題。將每個石頭視為圖中的一個節點，石頭之間的距離作為邊的權重。蛙跳距離實際上就是從起始節點到目標節點的所有路徑中，最大邊權重的最小值。可以使用 Floyd-Warshall 演算法來計算所有節點對之間的最短路徑，並在計算過程中找到滿足條件的最小最大邊權重。
Floyd-Warshall 演算法的核心思想是動態規劃，它通過迭代更新所有節點對之間的距離，最終得到所有節點對之間的最短路徑。在每次迭代中，它考慮是否通過中間節點 k 來縮短從節點 i 到節點 j 的路徑。
具體來說，程式碼首先計算出所有石頭之間的距離，並將其存儲在 fl 陣列中。然後，使用 Floyd-Warshall 演算法更新 fl 陣列，使得 fl[i][j] 儲存從石頭 i 到石頭 j 的蛙跳距離。最後，輸出從石頭 0 到石頭 1 的蛙跳距離。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是石頭的數量。Floyd-Warshall 演算法的時間複雜度為 O(n^3)。
- 空間複雜度: O(n^2)，其中 n 是石頭的數量。
fl陣列需要 O(n^2) 的空間來儲存所有節點對之間的距離。
程式碼
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int n,ca;
struct p{
double x,y;
};
p a[210];
double fl[210][210],ans;
double dis(int xx,int yy){
double xd=a[xx].x-a[yy].x,yd=a[xx].y-a[yy].y;
if(xd<0)xd*=-1;
if(yd<0)yd*=-1;
return sqrt(xd*xd+yd*yd);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
ans=0;
for(int i=0;i<210;++i)
for(int j=0;j<210;++j)
fl[i][j]=0;
for(int i=0;i<n;++i)
cin >> a[i].x >> a[i].y;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
if(i==j)fl[i][j]=0;
else fl[i][j]=dis(i,j);
}
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
double ds=fl[i][k];
if(ds<fl[k][j])ds=fl[k][j];
if(fl[i][j]>ds){
fl[i][j] = ds;
}
}
cout << "Scenario #" << ++ca << "\nFrog Distance = " << fixed << setprecision(3) << fl[0][1] << "\n\n";
}
}