TopCoder

User's AC Ratio

91.2% (62/68)

Submission's AC Ratio

26.7% (92/344)

Description

給定一個立體(x * y * z)的迷宮,某人自(1,1,1)走至(x,y,z),請求出一條最短路徑,若有多組解,任一組都可。

Input Format

第一列有三個正整數x, y, z(1 <= x, y, z <= 50)表示迷宮大小。 接下來包含z個矩陣, 每個矩陣有y列x行, 其中的值為0或1,0表示可以行走,1表示無法通行的格點。

Output Format

一條自(1,1,1)到(x,y,z)的最短路徑
Format (1,1,1)->(x1,y1,z1)->(x2,y2,z2)...->(x,y,z)
若是沒有路徑從(1,1,1)到(x,y,z)的話則輸出"no route"

Sample Input

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

Sample Output

(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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7