2013年7月23日 星期二

183 - Bit Maps

bitmap 是一種用在描述區域上的資料結構。

在圖形描述上,例如: bitmap 可以表示黑白兩色的圖形,以 1 表示黑色像素,而 0 表示白色像素,對於描述矩形的 bitmap 有兩種方法,第一種直接使用二維方式記錄 1 和 0,第二種的基礎建立在分解技術上,也就是常見的影像四分樹。

稍微細講一下第二種方法的內容,首先,如果整個區域都是黑色 1 的話,則會輸出 1,而全部都是白色 0,則會輸出 0,都不是以上兩者的話,即黑白兼有則輸出 D。在黑白兼有的情況下,將會繼續劃分成四個象限,四個象限被切割順序左上、右上、左下、右下,如果行列都是偶數的情況,則四個象限將會有相同的大小,如果行或列是奇數的話,則左邊將會多出一列(column),上方將會多出一行(row)。

而當只有一行或一列的區域中,將只能化成兩個象限(左邊跟右邊)。

寫一個程式讀入 bitmap 的其中一種描述方法,轉換成另外一種描述方法。

Input

輸入有多組測資,每組測資第一行第一個字符("B" or "D") 表示格式形態,以及兩個整數 row, column (0 <= row, column <= 200)表示圖形的維度,彼此間可能有數個空白隔開。

而接下來將會有一行或者數行的字串由 "1", "0", "D" 構成,除了最後一行,每行將會有 50 個字元,如果是 "B" 形態,順序是由左而右,由上而下的方式給予。

以單獨一行 "#" 代表結束。


Output

對於每組測資,輸出另一個種換的描述,而且輸出的格式按照輸入方式,而 row, column 輸出時向右對齊 4 個寬度。

輸出格式:一行最多占有 50 個字符,超過換一行。

Sample input

B 3  4
001000011011
D  2   3
DD10111
#

Sample output

D   3   4
D0D1001D101
B   2   3
101111