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
_____

---

原文出處