1154 . 3.黑白影像的四分樹表示法
TopCoder
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 1
4
0000
0100
0011
0011
0000
0100
0011
0011
Sample Output 1
g w g w w w b w b
Sample Input 2
4
1000
0110
0110
0000
1000
0110
0110
0000
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 Input 3
8
00001111
00001111
00101111
00101111
00000000
00000000
00000011
00001111
00001111
00001111
00101111
00101111
00000000
00000000
00000011
00001111
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
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |