2011年7月26日 星期二

784 - Maze Exploration

下圖a的四方形迷宮是由多個3x3的房間所組成,房間以通道連接。迷宮的牆面以任意字元表示,但表示牆面的字元不會是'*', '_', ' '(空白字元),例如下圖中以'x'表示牆面,房間與通道的地方以空白字元表示。
XXXXXXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXXXXXXXX
X   X   X   X   X   X             X###X###X###X   X   X
X           X   X   X             X###########X   X   X
X   X   X   X   X   X             X###X###X###X   X   X
XXXXXX XXX XXXXXXXXXX             XXXXXX#XXX#XXXXXXXXXX
X   X   X   X   X   X             X   X###X###X###X###X
X   X     *         X             X   X###############X
X   X   X   X   X   X             X   X###X###X###X###X
XXXXXXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXXXXXXXX
a) 輸入迷宮                                                         b) 輸出迷宮
Figure 1. 由3x3大小的房間所組成的迷宮

每個房間四週的寬度為3,且牆的厚度為1,這表示房間大小皆為3x3,且通道為1x1,而通道的門一定是在牆壁的中央。迷宮的四週不會有對外的通道。

有三個門的房間:
                       |
                     XX XX
                     X . X
               door - ...--  房間大小為3x3
                     X . X__
                     XXXXX  |
                       |___  牆的厚度為1
Figure 2. 有三個門的房間

本題請你表示出:從特定房間出發所能走訪的房間與通道,出發的房間的正中央會以'*'來表示,兩個房間必須要有通道連接才能相通,可走訪的房間與通道請以'#'來取代原先的空白字元。如上圖 b 所示。

Input

輸入的第一列有一個表示迷宮數量的整數,接下來每一列用來表示所有迷宮的地圖。
每組迷宮的大小可能不會相同,且不同迷宮以一列由'_'底線字元組成的字串隔開,每個迷宮最多以30列字串表示,且每列不超過80個字元。

Output

請以'#'標記出可走訪的房間與通道,並輸出此迷宮,輸出必須包含以底線組成的分隔線,請參考範例輸出。

Sample Input 

2
XXXXXXXXX
X   X   X
X *     X
X   X   X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X   X
X * X
X   X
XXXXX
_____

Sample Output 

XXXXXXXXX
X###X###X
X#######X
X###X###X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X###X
X###X
X###X
XXXXX
_____


原文出處

沒有留言:

張貼留言