內容
某遊樂場之園區是採棋盤式的規劃，由許多正方形區塊組成，每一格點上會有一種遊樂設施供遊客使用。
當遊客要從設施 A 移動到設施 B 時，必須沿著區塊四邊以步行方式前往，一個正方形區塊之一邊為一個單位距離。
遊樂場也提供若干條點對點之間的快速電梯通道，供遊客使用，此區間就不用步行。
遊客可採步行與電梯混和使用之方式以達最短之步行距離，快速到達終點。
在本題中，給定起點設施 A 與終點設施 B 之座標，找出一條移動路徑由 A 至 B，其步行距離最短,並且列出此路徑搭電梯之最少次數。
舉例來說，下圖為一個 6x7 共有 42 種設施之遊樂場，內部提供 5 條電梯通道(紅色虛線)。
當起點座標 A 為(5, 0)，終點座標 B 為(1, 6)時，可採以下之一種座標移動方式抵達終點：(5, 0)-步行-(5, 4)-電梯-(3, 6) -步行- (1, 6)，此時之步行距離為 6。
但若採另一種座標移動方式：(5, 0)-步行- (3, 0)-電梯-(1, 2)-步行-(0,2)-電梯-(1, 4)-步行-(1, 6)，則可以達成最短之步行距離為 5，此時所搭電梯的次數為 2。
輸入說明
第 1 列有 2 個數字 M、N，分別表示縱向與橫向格點之數目
第 2 列有 2 個數字，表示起點設施 A 之座標
第 3 列有 2 個數字，表示終點設施 B 之座標
第 4 列有 1 個數字，表示電梯通道之數目 K
第 5~(4+K)列有 4 個數字，表示各個電梯通道兩個端點之座標
輸出說明
輸出共有 2 個數字，第 1 個數字為最短之步行距離，第 2 個數字為最短路徑時最少之搭電梯次數，數字間以空白鍵隔開。
範例輸入
#1
6 7 5 0 1 6 5 3 0 1 2 0 2 1 4 5 2 2 3 4 2 3 5 5 4 3 6
範例輸出
#1
5 2
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1M
提示 ：
標籤:
出處:
109彰雲嘉學科能力
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||