TopCoder

Thumb 343jksfld
ltf0501
願與最重要之人能再次相會。

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

83.3% (15/18)

Description

一張黑白影像可以以一個二維陣列表示,將陣列的每個元素以一個位元表示其顏色,1代表黑色,0代表白色。然而在大多數情況下,我們發現一張黑白影像的中,相同的顏色通常會位在相鄰的位置;因此我們可以利用四分樹(quadtree)的表示法來記錄一張黑白影像,以得到比二維陣列較節省記憶體的表示法。

四分樹的表示法就是將目前欲表示的黑白影像區域,以十字形方式分割為四份,分別為東北方、西北方、西南方及東南方四個子區域。以圖一為例,當把整張大小為16×16的圖分割為四份時,東北方的恰好為一整塊的黑色,我們可以一個黑色的節點(圖二中的1號節點)表示這整個4×4的黑色區域。而西北方的4×4區域並非由同一色所組成,因此必須再進行分割;當我們以相同的方式遞迴地分割西北方的4×4區域,可得到圖二中第3、4、5號節點以及再下一層的9、10、11、12號節點。圖二中,黑色的節點表示黑色的像素,白色的節點表示白色的像素,圓圈表示內部節點。

當我們得到圖二的四分樹表示法後,可使用b, w, g三個符號分別代表黑色節點、白色節點及內部節點,依照深先(depth-first)表示法將四分樹符號輸出(依pre–order順序輸出)。因此,圖二的四分樹可表示成


g b g w w w g w b b w w g w w g w w b b b

請撰寫一個程式,將每張黑白影像的四分樹表示法,利用中b, w, g三個符號以深先表示法的結果列出。

Input Format

第一行為一個整數n,代表一張正方形黑白影像的寬度及高度。(n=2k,k為正整數,1<k≤7)。
接下來的n行代表影像中每一行的內容:0表示一個白色像素,1表示一個黑色像素。

Output Format

對每一個輸入的黑白影像,將其四分樹表示法以b, w, g三個符號,依深先表示法順序列出(每個輸出符號之間有一個空白隔開)。
※請注意不要輸出行尾的空白!

Sample Input

Sample Input #1:

4
0000
0100
0011
0011

Sample Input #2:

4
1000
0110
0110
0000

Sample Input #3:

8
00001111
00001111
00101111
00101111
00000000
00000000
00000011
00001111

Sample Output

Sample Output #1:

g w g w w w b w b

Sample Output #2:

g g w w b w g w b w b g b w w w g w b w w

Sample Output #3:

g b g w w w g w b b w w g w w g w w b b b

Hints

Problem Source

原TIOJ1154 / 93全國賽(prob 3)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536
1 30000 65536 65536
2 30000 65536 65536
3 30000 65536 65536
4 30000 65536 65536