1085 . 三維迷宮問題
TopCoder
Description
給定一個立體 $(x * y * z)$ 的迷宮，某人自 $(1,1,1)$ 走至 $(x,y,z)$，請求出一條最短路徑，若有多組解，任一組都可。
Input Format
第一列有三個正整數 $x, y, z\ (1 \le x, y, z \le 50)$ 表示迷宮大小。 接下來包含 $z$ 個矩陣， 每個矩陣有 $y$ 列 $x$ 行， 其中的值為 $0$ 或 $1$，$0$ 表示可以行走，$1$ 表示無法通行的格點。
Output Format
一條自 $(1,1,1)$ 到 $(x,y,z)$ 的最短路徑
Format $(1,1,1)\text{->}(x_1,y_1,z_1)\text{->}(x_2,y_2,z_2)\dots\text{->}(x,y,z)$
若是沒有路徑從 $(1,1,1)$ 到 $(x,y,z)$ 的話則輸出 "no route"
Sample Input 1
5 5 2
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 1 1 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 0 1 0
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 1 1 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 0 1 0
Sample Output 1
(1,1,1)->(2,1,1)->(3,1,1)->(4,1,1)->(5,1,1)->(5,1,2)->(5,2,2)->(5,3,2)->(4,3,2)->(3,3,2)->(3,4,2)->(3,5,2)->(3,5,1)->(4,5,1)->(5,5,1)->(5,5,2)
Hints
Problem Source
原TIOJ1085 / 94建中校內資訊能力競賽(prob 3)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 14 |
| 2 | 1 | 14 |
| 3 | 2 | 14 |
| 4 | 3 | 14 |
| 5 | 4 | 14 |
| 6 | 5 | 14 |
| 7 | 6 | 16 |