[UVA] 183 - Bit Maps
Bit Maps
| Bit Maps |
The bitmap is a data structure that arises in many areas of computing. In the area of graphics, for example, a bitmap can represent an image by having a 1 represent a black pixel and a 0 represent a white pixel.
Consider the following two ways of representing a rectangular bit map. In the first, it is simply represented as a two dimensional array of 1s and 0s. The second is based on a decomposition technique. First, the entire bit map is considered. If all bits within it are 1, a 1 is output. If all bits within it are 0, a 0 is output. Otherwise, a D is output, the bit map is divided into quarters (as described below), and each of those is processed in the same way as the original bit map. The quarters are processed in top left, top right, bottom left, bottom right order. Where a bit map being divided has an even number of rows and an even number of columns, all quarters have the same dimensions. Where the number of columns is odd, the left quarters have one more column than the right. Where the number of rows is odd the top quarters have one more row than the bottom. Note that if a region having only one row or one column is divided then two halves result, with the top half processed before the bottom where a single column is divided, and the left half before the right if a single row is divided.
Write a program that will read in bitmaps of either form and transform them to the other form.
Input
Input will consist of a series of bit maps. Each bit map begins with a line giving its format (``B'' or ``D'') and its dimensions (rows and columns). Neither dimension will be greater than 200. There will be at least one space between each of the items of information. Following this line will be one or more lines containing the sequence of ``1'', ``0'' and ``D'' characters that represent the bit map, with no intervening spaces. Each line (except the last, which may be shorter) will contain 50 characters. A ``B'' type bitmap will be written left to right, top to bottom. The file will be terminated by a line consisting of a single #.
Output
Output will consist of a series of bitmaps, one for each bit map of the input. Output of each bit map begins on a new line and will be in the same format as the input. The width and height are to be output right justified in fields of width four.
Sample input
B 3 4 001000011011 D 2 3 DD10111 #
Sample output
D 3 4 D0D1001D101 B 2 3 101111
題目描述：
描述一個影像的方法有兩種，直接描述或者使用影像四分樹。
假設(0,0)是左上角的點，而(row-1, col-1)是右下角的點，那麼描述順序是左上右上左下右下。
給定其中一種，轉換成另外一種。
影像四分樹給定的方式採用前序。
題目解法：
這題其實沒有特別困難，但是要處理輸入輸出就不容易，一行最多 50 個字元，輸入輸出都一樣的處理方式，但是麻煩在於如何處理輸入，要怎麼分辨是否為新的一筆，而不是測資資料。
輸出一行最多 50 字元。
在處理四分樹的輸出時，採用很慢的直接搜索(判斷D or 1 or 0)。因此運氣不好會到 O(n^2)，不過大體上不太可能。
#include <stdio.h>
#include <string.h>
int row, col;
char fmt[105], s[65536], g[256][256];
int idx = 0;
void color(int lx, int rx, int ly, int ry) {
if(lx > rx || ly > ry) return;
int i, j;
if(s[idx] == '0') {
for(i = lx; i <= rx; i++)
for(j = ly; j <= ry; j++)
g[i][j] = '0';
idx++;
return;
}
if(s[idx] == '1') {
for(i = lx; i <= rx; i++)
for(j = ly; j <= ry; j++)
g[i][j] = '1';
idx++;
return;
}
int mx = (lx+rx)/2, my = (ly+ry)/2;
idx++;
color(lx, mx, ly, my);
color(lx, mx, my+1, ry);
color(mx+1, rx, ly, my);
color(mx+1, rx, my+1, ry);
}
void dfs(int lx, int rx, int ly, int ry) {
if(lx > rx || ly > ry) return;
int i, j, v = g[lx][ly], same = 1;
for(i = lx; i <= rx; i++) {
for(j = ly; j <= ry; j++) {
if(g[i][j] != v)
same = 0, j = ry, i = rx;
}
}
if(same == 1) {
putchar(v);
idx++;
if(idx%50 == 0) puts("");
return;
}
int mx = (lx+rx)/2, my = (ly+ry)/2;
putchar('D');
idx++;
if(idx%50 == 0) puts("");
dfs(lx, mx, ly, my);
dfs(lx, mx, my+1, ry);
dfs(mx+1, rx, ly, my);
dfs(mx+1, rx, my+1, ry);
}
int main() {
int i, j;
char buf[65536];
gets(buf);
while(sscanf(buf, "%s %d %d", fmt, &row, &col) == 3) {
if(!strcmp(fmt, "#"))
break;
buf[0] = '\0';
if(fmt[0] == 'B') {
char ch = -1;
idx = 0;
while(idx < row*col && (ch = getchar())) {
if(ch != '\0' && ch != '\n')
s[idx++] = ch;
}
printf("D%4d%4d\n", row, col);
idx = 0;
for(i = 0; i < row; i++)
for(j = 0; j < col; j++)
g[i][j] = s[idx++];
idx = 0;
dfs(0, row-1, 0, col-1);
if(idx%50)
puts("");
if(row*col)
while(getchar() != '\n');
gets(buf);
} else {
idx = 0;
while(gets(buf)) {
if(buf[1] == ' ') break;
for(i = 0; buf[i]; i++)
s[idx++] = buf[i];
}
printf("B%4d%4d\n", row, col);
idx = 0;
color(0, row-1, 0, col-1);
idx = 0;
for(i = 0; i < row; i++) {
for(j = 0; j < col; j++) {
putchar(g[i][j]);
idx++;
if(idx%50 == 0) puts("");
}
}
if(idx%50)
puts("");
}
}
return 0;
}