d373: 5. 乳酪的誘惑
標籤 :
通過比率 : 43人/48人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-08-15 09:03

內容
這個問題跟傳統的老鼠走迷宮問題不太一樣,給定一個四方形的格點空間
x 座標與y 座標由左下角原點以0 開始往右和往上遞增,裡面有一個區域是鼠窩,另外有一個區域是乳酪屋
此外還有很多障礙物是用來阻擋鼠輩的橫行,也就是障礙物是不可穿越的。
在此空間裡可能沒有路可以從鼠窩走到乳酪屋,此種情況你必須回報沒有路徑
如果有路可以連接鼠窩跟乳酪屋的話,你必須算出從鼠窩走到乳酪屋的最短路徑。
老鼠的每一步只能往四個方向走:上、下、左、右,不能走對角方向。出發點與終點可以是鼠窩與乳酪屋的任何一個位置。
以圖一為例,鼠窩到乳酪屋的最短距離為15,由鼠窩裡圓圈所標示的點(10,2)往左出發走到乳酪屋中圓圈所標示的點(1,8)。
鼠窩與乳酪屋的形狀一定是一條直線,障礙物可以是一點可以是一條直線也可以是一個矩形區域
圖一中的障礙物是由三個點與兩條直線所構成,分別為點(2,6)、(3,5)、與(4,4)和線(4,3)~(7,3)與(7,4)~(7,9)。
在找尋最短路徑時,不要只派遣一隻老鼠出任務,這樣會累死這隻可憐的倒霉鼠的。

 
輸入說明
輸入的第一行為兩個整數,描述方形格點空間的大小,第一個表示行的數目,第二個表示列的數目
在此問題中行和列的數目都不會超過1000 (<=1000)。
接下來“.mb”表示後面用兩點來描述鼠窩的位置,每個點先x 座標再y 座標,兩個點沒有固定的先後排序。
接下來“.cb”表示後面用兩點來描述乳酪屋的位置,兩個點也沒有固定的先後排序。
最後“.bb”表示後面開始每一行描述一個障礙物的位置,不管是一點還是一條線都是用兩點來表示
最後以“.be”表示結束。
輸出說明
沒有路徑的話,輸出“no path”。有路徑的話輸出最短路徑距離。

範例輸入
以圖一為例,其輸入檔案如下:
14 10
.mb 10 4 10 1
.cb 1 8 4 8
.bb
2 6 2 6
3 5 3 5
4 4 4 4
4 3 7 3
7 9 7 4
.be
範例輸出
15
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 2.0s , <1K
不公開 測資點#1 (20%): 2.0s , <1M
不公開 測資點#2 (20%): 2.0s , <1M
不公開 測資點#3 (20%): 2.0s , <1K
不公開 測資點#4 (20%): 2.0s , <1K
提示 :
標籤:
出處:
96學年度全國資訊學科能力競賽 [管理者:
pcshic (PCSHIC)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」