Bitmap matrix processing in C

Question

I have an algorithm made to transform a bitmap matrix into an array. The logic behind it is to divide the matrix into smaller quadrants until reaching the units and for each quadrant, if all variables are equal to zero, it prints zero, if they are all equal to one, it prints one and otherwise it prints D. My problem is when there is a variable different from 1 or 0.

The use of recursion and the divide and conquer strategy is mandatory. Quadrants are processed in the order top left > top right > bottom left > bottom right

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);
    }
}

This is how it's called

    
    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;
    }

I tried this solution but when finding a value other than 1 or 0, instead of printing a D it goes into an infinite loop printing several Ds.

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

Input:

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

Output:

D0D1001D101
1
DD0101D0101D0101D0101

Answer 1

The code shown analyses every pixel at every layer. This gets to be expensive!

Consider a 256x256 array broken into 4 quadrants, each 128x128. Think it through:
1x(256x256) => 4x(128x128)
1x(128x128) => 4x(64x64)
1x(64x64) => 4x(32x32)
1x(32x32) => 4x(16x16)
1x(16x16) => 4x(8x8)
1x(8x8) => 4x(4x4)
1x(4x4) => 4x(2x2) ... and here is the base case

Count the layers. This is how many times the entire collection is analysed.

You might try writing your code so that the 4 calls to actually look at the data each return 00 when the 4 pixels examined are 0, return 11 when the 4 pixels are 1, and return 01 (or 10) when there a mixture of 0's and 1's.

The caller assembles the return values into a byte (ex: 00 11 01 00) representing the 4 quadrants from the lower layer. (Remember that the caller is actually one of four quadrants from the recursion layer above.) So, only 0x00000000 or 0x11111111 are "pure" collections of bits in the 4 quadrants below. Any other pattern represents a heterogenous collection in the 4 quadrants below. The caller can then return to its caller either 00, or 11, or 01.

As the recursion unwinds, each layer deals only with the 4 returned values from its lower layer.

Obviously most collections of bits would quickly tend toward a heterogenous result such as 01010101. This is a dull answer.

More interesting would be to assess whether any 4 quadrants are predominantly dark (1) or predominantly light (0) and having a majority vote of the 4 quadrants below form the value of the current layer of the recursion.