C 中的位图矩阵处理

Question

我有一个算法可以将位图矩阵转换为数组。其背后的逻辑是将矩阵划分为更小的象限，直到达到单位，对于每个象限，如果所有变量都等于 0，则打印 0，如果它们都等于 1，则打印 1，否则打印 D。我的问题是当变量不同于 1 或 0 时。

必须使用递归和分治策略。象限按左上 > 右上 > 左下 > 右下的顺序处理

void processBitmap(char bitmap[][300], int linhaStart, int linhaEnd, int colStart, int colEnd) {
    if (linhaStart > linhaEnd || colStart > colEnd) {
        return;
    }
    int allOnes = 1;
    int allZeros = 1;

    for (int i = linhaStart; i <= linhaEnd; i++) {
        for (int j = colStart; j <= colEnd; j++) {
            if (bitmap[i][j] == '0') {
                allOnes = 0;
            } else {
                allZeros = 0;
            }
        }
    }
  
    if (allOnes) {
        printf("1");
    }
    else if (allZeros) {
        printf("0");
    }
    else {
        int midLinha = (linhaStart + linhaEnd) / 2;
        int midCol = (colStart + colEnd) / 2;

        printf("D");
        processBitmap(bitmap, linhaStart, midLinha, colStart, midCol);
        processBitmap(bitmap, linhaStart, midLinha, midCol + 1, colEnd);
        processBitmap(bitmap, midLinha + 1, linhaEnd, colStart, midCol);
        processBitmap(bitmap, midLinha + 1, linhaEnd, midCol + 1, colEnd);
    }
}

这就是它的名字

    
    int main() {
        int N;
        scanf("%d", &N);
    
        while (N--) {
            int L, C;
            scanf("%d %d", &L, &C);
    
            char bitmap[300][300];
    
            scanf("%*c");
    
            for (int i = 0; i < L; i++) {
                fgets(bitmap[i], sizeof(bitmap[i]), stdin);
            }
    
            for (int i = 0; i < L; i++) {
                if (bitmap[i][C] == '\n') {
                    bitmap[i][C] = '\0';
                }
            }
    
            processBitmap(bitmap, 0, L - 1, 0, C - 1);
            printf("\n");
        }
    
        return 0;
    }

我尝试了这个解决方案，但是当找到 1 或 0 以外的值时，它不是打印 D，而是进入无限循环，打印几个 D。

if (bitmap[i][j] == '0') {
                allOnes = 0;
            } else if (bitmap[i][j] == '1') {
                allZeros = 0;
            } else {
              allOnes = 0;
              allZeros = 0;
            }

输入：

3
3 4
0010
0001
1011
1 1
1
4 4
0101
0101
0101
0101

输出：

D0D1001D101
1
DD0101D0101D0101D0101

Answer 1

显示的代码分析每一层的每个像素。这会很贵！

考虑将 256x256 阵列分为 4 个象限，每个象限为 128x128。想清楚了：
1x(256x2560 => 4x(128128)
1x(128128) => 4x(64x64)
1x(64x64) => 4x(32x32)
1x(32x32) => 4x(16x16)
1x(16x16) => 4x(8x8)
1x(8x8) => 4x(4x4)
1x(4x4) => 4x(2x2) ...这是基本情况

数数层数。这是整个集合被分析的次数。

您可以尝试编写代码，以便实际查看数据的 4 个调用在检查的 4 个像素为 0 时返回 00，在检查的 4 个像素为 1 时返回 11，在混合时返回 01（或 10） 0 和 1。

调用者将返回值组装成一个字节（例如：00 11 01 00），表示下层的 4 个象限。 （请记住，调用者实际上是上面递归层的四个象限之一。）因此，只有 0x00000000 或 0x11111111 是下面 4 个象限中的“纯”位集合。任何其他模式都代表以下 4 个象限中的异质集合。然后，呼叫者可以返回给呼叫者 00、11 或 01。

随着递归展开，每一层仅处理来自其下层的 4 个返回值。

显然，大多数位的集合很快就会倾向于异质结果，例如 01010101。这是一个乏味的答案。

更有趣的是评估任何 4 个象限是否是主要暗（1）或主要是亮（0），并且以下 4 个象限的多数票形成了当前递归层的值。