C语言递归Flood Fill算法：ASCII艺术递增字符填充异常求助

程序要求 #

• 在以*代表墙壁的房间中定位字符A（确保房间中必有一个A）；
• 从A开始，用递增字符填充房间空白区域，到Z后保持用Z填充，示例输出如下：

*****
*DCB*
***A*
*DCB*
*****

现有代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct room{
    char **array;
    int rows;
    int cols;
} room;

void printRoom(room room);
int *findA(room room);
void floodFill(room room, int x, int y, char paint);

int main(int argc, char *argv[]){
    // Make a new room
    room newRoom;
    newRoom.rows = 5;
    newRoom.cols = 5;

    // Allocate memory for the array
    newRoom.array = malloc(newRoom.rows * sizeof(char*));
    for(int i = 0; i < newRoom.rows; i++){
        newRoom.array[i] = malloc(newRoom.cols * sizeof(char));
    }

    // Fill the first array with "*****"
    for(int i = 0; i < newRoom.cols; i++){
        newRoom.array[0][i] = '*';
    }

    // Fill the second array with "*   *"
    newRoom.array[1][0] = '*';
    newRoom.array[1][1] = ' ';
    newRoom.array[1][2] = ' ';
    newRoom.array[1][3] = ' ';
    newRoom.array[1][4] = '*';

    // Fill the third array with "**A*"
    newRoom.array[2][0] = '*';
    newRoom.array[2][1] = '*';
    newRoom.array[2][2] = '*';
    newRoom.array[2][3] = 'A';
    newRoom.array[2][4] = '*';

    // Fill the fourth array with "*   *"
    newRoom.array[3][0] = '*';
    newRoom.array[3][1] = ' ';
    newRoom.array[3][2] = ' ';
    newRoom.array[3][3] = ' ';
    newRoom.array[3][4] = '*';

    // Fill the fifth array with "*****"
    for(int i = 0; i < newRoom.cols; i++){
        newRoom.array[4][i] = '*';
    }
    
    printf("Before\n");
    printRoom(newRoom);

    // Find the A
    int *a = findA(newRoom);
    printf("A is at %d, %d\n", a[0], a[1]);

    // Flood fill the room
    floodFill(newRoom, a[0], a[1], 'A');

    printf("\nAfter\n");
    printRoom(newRoom);
    
    return 0;
}

int *findA(room room){
    int *location = malloc(2 * sizeof(int));
    for(int i = 0; i < room.rows; i++){
        for(int j = 0; j < room.cols; j++){
            if(room.array[i][j] == 'A'){
                location[0] = i;
                location[1] = j;
            }
        }
    }
    return location;
}

void floodFill(room room, int x, int y, char paint){
    // If the current position is a wall, return
    if(room.array[x][y] == '*'){
        return;
    }

    // If the current position is already painted, return
    if(room.array[x][y] == paint){
        return;
    }

    if(x < 0 || x >= room.rows || y < 0 || y >= room.cols){
        return;
    }

    // Paint the current position
    room.array[x][y] = paint;

    // Flood fill the left position
    floodFill(room, x, y + 1, paint);
    floodFill(room, x, y - 1, paint);
    floodFill(room, x + 1, y, paint);
    floodFill(room, x - 1, y, paint);
}

void printRoom(room room){
    for(int i = 0; i < room.rows; i++){
        for(int j = 0; j < room.cols; j++){
            printf("%c", room.array[i][j]);
        }
        printf("\n");
    }
}

当前输出 #

Before
*****
*   *
***A*
*   *
*****
A is at 2, 3

After
*****
*   *
***A*
*   *
*****

问题分析 #

1. 结构体传值问题：C语言中结构体按值传递时会创建副本，floodFill函数修改的是副本的数组，原数组完全没变化，这是填充无效果的核心原因。
2. 边界检查顺序错误：先访问数组再做边界检查，可能导致越界访问。
3. 递归逻辑缺陷：
   • 首次调用时，当前位置是A，触发room.array[x][y] == paint的条件直接返回，未处理周围区域；
   • 固定使用paint='A'填充，无法实现字符递增的要求；
   • 坐标交换后出现部分填充，是因为传入了错误的行/列坐标，导致起始位置错误。

解决方案 #

关键修改点 #

• 结构体传指针：让floodFill直接修改原数组，而非副本；
• 调整边界检查顺序：先判断坐标是否越界，避免非法数组访问；
• 重构递归逻辑：传递当前填充字符，每递归一层递增字符（到Z后停止递增），区分初始A和待填充空白区域。

修改后的代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct room{
    char **array;
    int rows;
    int cols;
} room;

void printRoom(room room);
int *findA(room room);
void floodFill(room *room, int x, int y, char currentChar);

int main(int argc, char *argv[]){
    room newRoom;
    newRoom.rows = 5;
    newRoom.cols = 5;

    newRoom.array = malloc(newRoom.rows * sizeof(char*));
    for(int i = 0; i < newRoom.rows; i++){
        newRoom.array[i] = malloc(newRoom.cols * sizeof(char));
    }

    for(int i = 0; i < newRoom.cols; i++){
        newRoom.array[0][i] = '*';
    }

    newRoom.array[1][0] = '*';
    newRoom.array[1][1] = ' ';
    newRoom.array[1][2] = ' ';
    newRoom.array[1][3] = ' ';
    newRoom.array[1][4] = '*';

    newRoom.array[2][0] = '*';
    newRoom.array[2][1] = '*';
    newRoom.array[2][2] = '*';
    newRoom.array[2][3] = 'A';
    newRoom.array[2][4] = '*';

    newRoom.array[3][0] = '*';
    newRoom.array[3][1] = ' ';
    newRoom.array[3][2] = ' ';
    newRoom.array[3][3] = ' ';
    newRoom.array[3][4] = '*';

    for(int i = 0; i < newRoom.cols; i++){
        newRoom.array[4][i] = '*';
    }
    
    printf("Before\n");
    printRoom(newRoom);

    int *a = findA(newRoom);
    printf("A is at %d, %d\n", a[0], a[1]);

    // 传结构体指针，使用正确的坐标
    floodFill(&newRoom, a[0], a[1], 'A');

    printf("\nAfter\n");
    printRoom(newRoom);
    
    // 释放内存（避免泄漏）
    free(a);
    for(int i = 0; i < newRoom.rows; i++){
        free(newRoom.array[i]);
    }
    free(newRoom.array);
    
    return 0;
}

int *findA(room room){
    int *location = malloc(2 * sizeof(int));
    for(int i = 0; i < room.rows; i++){
        for(int j = 0; j < room.cols; j++){
            if(room.array[i][j] == 'A'){
                location[0] = i;
                location[1] = j;
                break; // 找到后直接退出，优化效率
            }
        }
    }
    return location;
}

void floodFill(room *room, int x, int y, char currentChar){
    // 1. 先做边界检查
    if (x < 0 || x >= room->rows || y < 0 || y >= room->cols) {
        return;
    }
    // 2. 墙壁直接返回
    if (room->array[x][y] == '*') {
        return;
    }
    // 3. 非空白且不是初始A，说明已填充过，返回
    if (room->array[x][y] != ' ' && !(currentChar == 'A' && room->array[x][y] == 'A')) {
        return;
    }

    // 填充空白区域，初始A保留
    if (room->array[x][y] == ' ') {
        room->array[x][y] = currentChar;
    }

    // 计算下一个字符，到Z后不再递增
    char nextChar = (currentChar < 'Z') ? currentChar + 1 : 'Z';

    // 递归四个方向
    floodFill(room, x, y + 1, nextChar);
    floodFill(room, x, y - 1, nextChar);
    floodFill(room, x + 1, y, nextChar);
    floodFill(room, x - 1, y, nextChar);
}

void printRoom(room room){
    for(int i = 0; i < room.rows; i++){
        for(int j = 0; j < room.cols; j++){
            printf("%c", room.array[i][j]);
        }
        printf("\n");
    }
}

修改后输出 #

Before
*****
*   *
***A*
*   *
*****
A is at 2, 3

After
*****
*DCB*
***A*
*DCB*
*****

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