回分類題庫
d146: 資料結構98程式6.4
出處:

Difficulity : N/A
Accepted : 13 Times | Submit :184 Times | Clicks : 1324
Accepted : 9 Users | Submit : 74 Users | Accepted rate : 12%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2010-01-06 12:44

Content :

Keroro 的浮木跳躍


「宇宙侵略軍特殊先鋒部隊」由Keroro 軍曹領軍,潛入愛爾普藍星。愛爾普藍星上有條寬闊的愛爾普藍
河,河面上有不少由上游漂流下來的浮木。Keroro 因此想藉著水流靜止時,在浮木間跳躍。但是Keroro
的凌空跳躍只能往直行的方向跳躍,不能往歪斜的方向跳躍。當然,Keroro 可以在浮木上輕鬆的走動。
例 如:圖一有8 條浮木,A, B, C, D, E, F, G, H。Keroro 由浮木A 可以跳躍至浮木D 或浮木F,但無法直接斜跳至浮木B, C, E, G, H。如果Keroro 想由浮木A 跳躍至浮木H,Keroro 可以先後經過浮木D, F, G,接到達浮木H。也可以經過浮木D, G 到達H。還可以經過浮木F, G 到達H。當然也可以由經由浮木D, F, G, B, E 跳至浮木H。因此Keororo 有很多種方式由浮木A 跳躍至浮木H。但Keroro 最少只要3 次
就可以由浮木A 跳躍至浮木H(A  D  G  H 或A  F  G  H)。
已知浮木在河面上的位置,請利用Graph (Adjacency Matrix 或Adjacency List 皆可)來協助Keroro 找出由點浮木到達終點浮木的最少跳躍次數。

 

Input :

輸入的第一行為浮木的個數N, N 為正整數,2 <= N <= 1000。
第 2 行至第(N+1)行為每個浮木的端點座標X 與Y,X, Y 為正整數,1<= X < Y <= 10000,X, Y 之間以一個空白隔開。其中,第 2 行為起點浮木,第(N+1)行為終點浮木。

Output :

輸出為一正整數M,1 <= M <= (N-1),代表由起點浮木至終點浮木的最少跳躍次數。

Sample Input :

[輸入範例一]
8
1 4
8 11
5 7
3 6
9 13
2 6
5 9
8 14

[輸入範例二]
8
8 11
1 4
5 7
3 6
9 13
2 6
8 14
5 9

Sample Output :

[輸出範例一]
3

[輸出範例二]
1

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
沒有解題記錄 31115. henryokc (4 ms , 276KB)
35357. MK (6 ms , 280KB)
34327. QQ (6 ms , 280KB)
35906. cp99703050 (8 ms , 312KB)
35342. MK (8 ms , 282KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡