內容
這個問題跟傳統的老鼠走迷宮問題不太一樣，給定一個四方形的格點空間
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”。有路徑的話輸出最短路徑距離。
範例輸入
#1
以圖一為例，其輸入檔案如下: 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
範例輸出
#1
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
不公開 測資點#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
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||