題目(4) 迷宮問題

執行檔	maze.exe	輸入檔	maze.in
執行時間限制	30秒	輸出檔	maze.out

走迷宮一向是深受人喜愛的遊戲, 在這個題目中, 你必須找出一個三維迷宮中最短的走法.

在輸入資料中, 每個迷宮的第一行有三個數字, 表示迷宮的長 L, 寬 W, 高 H. 接下來有 H 個區塊, 每個區塊有 W 行, 每行有 L 個數字用空白隔開, 表示迷宮的 (L, W, H). (L, W, H <= 100) 如果該數字為 0 表示該格子為可通行, 1 表示該格子為不可通行. 測試資料中可能有多個迷宮, 每個迷宮中間有一空白行分隔. 檔案結尾為 EOF. 對於每個迷宮, 你必須輸出從座標 (1, 1, 1) 到 座標 (L, W, H) 的最短路徑, 每個迷宮一行. 輸出的格式為

(1,1,1)->(x,y,z)->....->(L,W,H)
 

如果無法走到終點, 你必須輸出 "no route"

注意! 在迷宮中你只能往上,下,左,右,前,後六個方向移動, 而且不可以移出迷宮的範圍. 例如: 如果你在 (3, 4, 5) 的位置, 則你只能往 (2,4,5), (4,4,5), (3,3,5), (3,5,5), (3,4,4), (3,4,6)這六個位置移動 (假設它們沒有超過迷宮範圍而且是可通行的).

底下是一個 4×3×2 的迷宮:

　

第一層

第二層

輸入的測試資料為:

 4 3 2
 0 1 1 0
 0 0 1 0
 0 1 0 0
 1 0 1 0
 1 1 1 1
 0 0 0 0
 

正確答案為:

 
 (1,1,1)->(1,2,1)->(1,3,1)->(1,3,2)->(2,3,2)->(3,3,2)->(4,3,2)

範例輸入

 
 4 3 2
 0 1 1 0
 0 0 1 0
 0 1 0 0
 1 0 1 0
 1 1 1 1
 0 0 0 0
 
 2 2 3
 0 1
 0 1
 1 1
 0 0
 1 1
 1 0
 
 2 2 1
 0 1
 1 1
 

範例輸出

 
 (1,1,1)->(1,2,1)->(1,3,1)->(1,3,2)->(2,3,2)->(3,3,2)->(4,3,2)
 (1,1,1)->(1,2,1)->(1,2,2)->(2,2,2)->(2,2,3)
 no route