C语言Bitmap矩阵处理问题：非0/1值引发无限递归输出D

问题概述 #

实现了基于递归分治的Bitmap矩阵转字符串算法：将矩阵划分为更小象限直至单元，全0输出0，全1输出1，否则输出D，处理顺序为左上→右上→左下→右下。但代码处理非全0/1的象限（或存在非0/1元素）时，陷入无限循环输出大量D，修改判断逻辑后问题仍存在。

原代码 #

处理函数 #

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

修改尝试的判断逻辑 #

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

问题根源 #

1. 无限递归触发条件：当矩阵中存在非0/1的字符（如'\0'、'\n'，由输入处理不严谨导致），单个元素会被判定为既非全0也非全1，进入递归分支。但单个元素划分后，四个子象限中仅一个为原元素，其余三个因范围无效直接返回，导致原元素被反复递归处理，无限输出D。
2. 输入处理缺陷：fgets会读取换行符，若行长度恰好等于C，bitmap[i][C]会被设为'\0'，但如果输入行长度不足C，后续位置会残留垃圾值，这些非0/1字符会触发上述问题。

修复方案 #

方案1：添加单个元素终止判断 #

在递归函数开头，先判断当前象限是否为单个元素，直接输出对应字符（避免递归）：

void processBitmap(char bitmap[][300], int linhaStart, int linhaEnd, int colStart, int colEnd) {
    if (linhaStart > linhaEnd || colStart > colEnd) {
        return;
    }
    // 单个元素直接输出，避免无限递归
    if (linhaStart == linhaEnd && colStart == colEnd) {
        printf("%c", bitmap[linhaStart][colStart]);
        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 if (bitmap[i][j] == '1') {
                allZeros = 0;
            } else {
                allOnes = 0;
                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);
    }
}

方案2：优化输入处理，确保仅读取有效0/1字符 #

修改主函数的输入逻辑，只读取每行前C个字符，避免残留换行符或垃圾值：

int main() {
    int N;
    scanf("%d", &N);

    while (N--) {
        int L, C;
        scanf("%d %d", &L, &C);

        char bitmap[300][300];
        char temp[301]; // 临时存储每行输入

        scanf("%*c");

        for (int i = 0; i < L; i++) {
            fgets(temp, sizeof(temp), stdin);
            // 只复制前C个字符到bitmap，确保都是0/1
            strncpy(bitmap[i], temp, C);
            bitmap[i][C] = '\0'; // 手动终止字符串
        }

        processBitmap(bitmap, 0, L - 1, 0, C - 1);
        printf("\n");
    }

    return 0;
}

验证结果 #

将两个修复方案结合后，运行输入示例可得到预期输出，且不会出现无限循环问题。

内容的提问来源于stack exchange，提问作者Brennofsr