[最短路徑]NOIP模擬題：奇怪的電梯 lift 解題報告

問題描述

呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第 i 層樓 (1<=i<=N) 上有一個數字 Ki(0<=Ki<=N) 。電梯只有四個按鈕：開，關，上，下。上下的層數等於當前樓層上的那個數字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如： 3 3 1 2 5 代表了 Ki(K1=3,K2=3,……) ，從一樓開始。在一樓，按 “ 上 ” 可以到 4 樓，按 “ 下 ” 是不起作用的，因爲沒有 -2 樓。那麼，從 A 樓到 B 樓至少要按幾次按鈕呢？

輸入

輸入文件共有二行，第一行爲三個用空格隔開的正整數，表示 N,A,B(1≤N≤200, 1≤A,B≤N) ，第二行爲 N 個用空格隔開的正整數，表示 Ki 。

輸出

輸出文件僅一行，即最少按鍵次數 , 若無法到達，則輸出 -1 。

樣例

lift.in

5 1 5

3 3 1 2 5

lift.out

3

【分析】

做這題方法很多，可以用搜索，最短路也行。

我用的是Floyd算法，三層循環，很好寫，呵呵。

開一個Mat數組，表示鄰接矩陣，Mat[i,j]初始化為-1（i!=j），Mat[i,i]初始化為0。

讀入時，把每個樓層能到達的樓層置為1。

然後Floyd就行了。

最後輸出Mat[A][B]。

【我的代碼】

#include <iostream>
#include <cstdio>
using namespace std;
int A,B;
int Mat[201][201];
int N;

void init()
{
    scanf("%d %d %d\n",&N,&A,&B);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Mat[i][j]=-1;
   
    int tmp;
    for (int i=1;i<=N;i++)
    {
        cin>>tmp;
        if(i-tmp>=1)
            Mat[i][i-tmp]=1;
        if(i+tmp<=N)
            Mat[i][i+tmp]=1;
    }
}

void Floyd() 
{ 
    int temp; 
    for (int k=1;k<=N;k++)   
    {   
        for(int i=1;i<=N;i++)   
        {   
            for(int j=1;j<=N;j++)   
            {   
                if ( Mat[i][k]!=-1 && Mat[k][j]!=-1)   
                {   
                    temp=Mat[i][k]+Mat[k][j];  
                    if ( (Mat[i][j]==-1) || ( Mat[i][j]>temp ) )   
                        Mat[i][j]=temp;   
                }   
            }   
        }   
    }   
} 

int main()
{
    freopen("lift.in","r",stdin);
    freopen("lift.out","w",stdout);
    init();
    Floyd();
    if(A==B)
        cout<<0<<endl;
    else
        cout<<Mat[A][B]<<endl;
    return 0;
}