2011年10月22日 星期六

705 - Slash Maze


利用斜線(/)與反斜線(\)可用來產生一組迷宮,如下圖所示:

本題著重在探討迷宮中的封閉路徑,計算封閉路徑總數及其中最長的路徑長度,如上圖中有兩個封閉路徑,路徑長度是以小方格的數目來做計算。上圖中的最長路徑長度為16,最短的路徑長度為4。

Input

輸入資料會包含多組迷宮資訊,每組迷宮的第一列有兩個整數 w 與 h (1 <= w, h <= 75),表示迷宮的寬度與長度。接下來的 h 列,每列有 w 個'/'或'\'字元表示迷宮。當 w = h = 0 表示測試資料結束。

Output

請對每組測試資料輸出一列"Maze #n:",其中 n 表示迷宮編號,接下來輸出"k Cycles; the longest has length l.",其 中 k 表示封閉路徑數,l 表示最長封閉路徑長度。若迷宮中沒有任何封閉路徑,請輸出"There are no cycles."。

請在每組輸出資料後多輸出一空白列。

Sample Input 

6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
0 0

Sample Output 

Maze #1:
2 Cycles; the longest has length 16.

Maze #2:
There are no cycles.


原文出處

沒有留言:

張貼留言