基于ASCII的C语言递归泛洪填充：如何实现字符向外扩散填充？

API 探路者

2026-8-18

问题

之前实现了基于ASCII艺术的C语言递归DFS泛洪填充算法，能正确填充空间，但字符填充呈现单向延伸的视觉效果，不符合预期。

现有程序示例代码如下：

#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);
room buildRoom();

int main(int argc, char *argv[]){

    // Make a new room
    room newRoom = buildRoom();

    printf("Before\n");
    printRoom(newRoom);

    // Find the A
    int *a = findA(newRoom);

    // Print the A
    printf("A is at %d, %d\n", a[0], a[1]);

    // Set current position to ' '
    newRoom.array[a[0]][a[1]] = ' ';

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

    // Print the room
    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){

    /* Base cases */
    if(x < 0 || x >= room.rows || y < 0 || y >= room.cols) return;
    if(room.array[x][y] != ' ') return;

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

    if(paint < 'Z') paint++;

    /* Recursive calls */
    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");
    }
}

room buildRoom(){

    room newRoom;
    int row = 12;
    int col = 14;

    newRoom.rows = row;
    newRoom.cols = col;

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

    char *row1 =     "**************";
    char *row2 =     "*  A         *";
    char *row3 =     "* **** ***** *";
    char *row4 =     "* *    *   * *";
    char *row5 =     "* * **** *** *";
    char *row6 =     "* * *  * *   *";
    char *row7 =     "*      * * ***";
    char *row8 =     "* **** * * * *";
    char *row9 =     "* *    * * ***";
    char *row10 =    "*** ****** * *";
    char *row11 =    "* *        * *";
    char *row12 =    "**************";

    int i;

    /* Make room.newArray[0][] = row1 */
    for(i = 0; i < col; i++){
        newRoom.array[0][i] = row1[i];
    }

    /* Make room.newArray[1][] = row2 */
    for(i = 0; i < col; i++){
        newRoom.array[1][i] = row2[i];
    }

    /* Make room.newArray[2][] = row3 */
    for(i = 0; i < col; i++){
        newRoom.array[2][i] = row3[i];
    }

    /* Make room.newArray[3][] = row4 */
    for(i = 0; i < col; i++){
        newRoom.array[3][i] = row4[i];
    }

    /* Make room.newArray[4][] = row5 */
    for(i = 0; i < col; i++){
        newRoom.array[4][i] = row5[i];
    }

    /* Make room.newArray[5][] = row6 */
    for(i = 0; i < col; i++){
        newRoom.array[5][i] = row6[i];
    }

    /* Make room.newArray[6][] = row7 */
    for(i = 0; i < col; i++){
        newRoom.array[6][i] = row7[i];
    }

    /* Make room.newArray[7][] = row8 */
    for(i = 0; i < col; i++){
        newRoom.array[7][i] = row8[i];
    }

    /* Make room.newArray[8][] = row9 */
    for(i = 0; i < col; i++){
        newRoom.array[8][i] = row9[i];
    }

    /* Make room.newArray[9][] = row10 */
    for(i = 0; i < col; i++){
        newRoom.array[9][i] = row10[i];
    }

    /* Make room.newArray[10][] = row11 */
    for(i = 0; i < col; i++){
        newRoom.array[10][i] = row11[i];
    }

    /* Make room.newArray[11][] = row12 */
    for(i = 0; i < col; i++){
        newRoom.array[11][i] = row12[i];
    }
    
    return newRoom;
}

当前程序输出：

Before
**************
*  A         *
* **** ***** *
* *    *   * *
* * **** *** *
* * *  * *   *
*      * * ***
* **** * * * *
* *    * * ***
*** ****** * *
* *        * *
**************
A is at 1, 3

After
**************
*CBAZZZZZZZZZ*
*D****Z*****Z*
*E*ZZZZ*   *Z*
*F*Z**** ***Z*
*G*Z*ON* *ZZZ*
*HIJKLM* *Z***
*I****N* *Z* *
*J*RQPO* *Z***
***S******Z* *
* *TUVWXYZZ* *
**************

期望实现的填充效果是字符从中心A向外扩散：A被B包围，B被C包围，依此类推，示例如下：

**************
*CBABCDEFGHIJ*
*D****E*****K*
*E*IHGF*   *L*
*F*J**** ***M*
*G*K*MN* *PON*
*HIJKLM* *Q***
*I****N* *R* *
*J*RQPO* *S***
***S******T* *
* *TUVWXWVU* *
**************

已知DFS无法实现这种逐层扩散的效果，BFS（广度优先搜索）可以达成，但不知道如何在现有代码中修改，需要技术思路和实现方案。

解决方案

核心思路

DFS是深度优先，会沿着一条路径走到头再回溯，导致字符单向延伸；而BFS是广度优先，会先处理完当前层的所有节点，再处理下一层，正好符合从中心向外逐层扩散的需求。要实现BFS，需要用队列来存储每一层的坐标，每次处理队列中的所有节点，完成当前层的填充后，再进入下一层并递增字符。

具体修改步骤

定义队列结构，用于存储待处理的坐标（x,y）
替换原递归的floodFill函数为BFS版本
调整字符递增逻辑：每处理完一层的所有节点后，再递增字符

修改后的完整代码

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

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

// 队列节点结构，存储坐标
typedef struct Node {
    int x;
    int y;
    struct Node* next;
} Node;

// 队列结构
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// 队列操作函数
Queue* createQueue();
void enqueue(Queue* q, int x, int y);
Node* dequeue(Queue* q);
int isQueueEmpty(Queue* q);
void freeQueue(Queue* q);

void printRoom(room room);
int *findA(room room);
void floodFill(room room, int startX, int startY, char startPaint);
room buildRoom();

int main(int argc, char *argv[]){
    room newRoom = buildRoom();

    printf("Before\n");
    printRoom(newRoom);

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

    newRoom.array[a[0]][a[1]] = ' ';
    floodFill(newRoom, a[0], a[1], 'A');

    printf("\nAfter\n");
    printRoom(newRoom);

    free(a);
    // 释放room内存，避免泄漏
    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;
            }
        }
    }
    return location;
}

void floodFill(room room, int startX, int startY, char startPaint){
    // 边界检查
    if(startX < 0 || startX >= room.rows || startY < 0 || startY >= room.cols){
        return;
    }
    if(room.array[startX][startY] != ' '){
        return;
    }

    Queue* q = createQueue();
    // 初始化：填充起始点并加入队列
    room.array[startX][startY] = startPaint;
    enqueue(q, startX, startY);

    char currentPaint = startPaint;
    // 四个方向：上下左右
    int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    while(!isQueueEmpty(q)){
        // 获取当前层的节点数量，确保处理完当前层再递增字符
        int levelSize = 0;
        Node* temp = q->front;
        while(temp != NULL){
            levelSize++;
            temp = temp->next;
        }

        // 处理当前层的所有节点
        for(int i=0; i<levelSize; i++){
            Node* node = dequeue(q);
            int x = node->x;
            int y = node->y;
            free(node);

            // 遍历四个方向
            for(int d=0; d<4; d++){
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                // 检查边界和是否可填充
                if(nx >=0 && nx < room.rows && ny >=0 && ny < room.cols 
                   && room.array[nx][ny] == ' '){
                    room.array[nx][ny] = currentPaint;
                    enqueue(q, nx, ny);
                }
            }
        }

        // 当前层处理完，字符递增（不超过'Z'）
        if(currentPaint < 'Z'){
            currentPaint++;
        }
    }

    freeQueue(q);
}

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

room buildRoom(){
    room newRoom;
    int row = 12;
    int col = 14;

    newRoom.rows = row;
    newRoom.cols = col;

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

    char *row1 =     "**************";
    char *row2 =     "*  A         *";
    char *row3 =     "* **** ***** *";
    char *row4 =     "* *    *   * *";
    char *row5 =     "* * **** *** *";
    char *row6 =     "* * *  * *   *";
    char *row7 =     "*      * * ***";
    char *row8 =     "* **** * * * *";
    char *row9 =     "* *    * * ***";
    char *row10 =    "*** ****** * *";
    char *row11 =    "* *        * *";
    char *row12 =    "**************";

    int i;
    for(i = 0; i < col; i++) newRoom.array[0][i] = row1[i];
    for(i = 0; i < col; i++) newRoom.array[1][i] = row2[i];
    for(i = 0; i < col; i++) newRoom.array[2][i] = row3[i];
    for(i = 0; i < col; i++) newRoom.array[3][i] = row4[i];
    for(i = 0; i < col; i++) newRoom.array[4][i] = row5[i];
    for(i = 0; i < col; i++) newRoom.array[5][i] = row6[i];
    for(i = 0; i < col; i++) newRoom.array[6][i] = row7[i];
    for(i = 0; i < col; i++) newRoom.array[7][i] = row8[i];
    for(i = 0; i < col; i++) newRoom.array[8][i] = row9[i];
    for(i = 0; i < col; i++) newRoom.array[9][i] = row10[i];
    for(i = 0; i < col; i++) newRoom.array[10][i] = row11[i];
    for(i = 0; i < col; i++) newRoom.array[11][i] = row12[i];
    
    return newRoom;
}

// 队列实现
Queue* createQueue(){
    Queue* q = malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, int x, int y){
    Node* newNode = malloc(sizeof(Node));
    newNode->x = x;
    newNode->y = y;
    newNode->next = NULL;

    if(q->rear == NULL){
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

Node* dequeue(Queue* q){
    if(q->front == NULL) return NULL;

    Node* temp = q->front;
    q->front = q->front->next;

    if(q->front == NULL){
        q->rear = NULL;
    }
    return temp;
}

int isQueueEmpty(Queue* q){
    return q->front == NULL;
}

void freeQueue(Queue* q){
    while(!isQueueEmpty(q)){
        Node* temp = dequeue(q);
        free(temp);
    }
    free(q);
}

关键代码解释

队列结构：用链表实现简单队列，负责存储每一层的坐标节点，保证BFS的顺序处理。
分层处理逻辑：每次循环先获取当前队列的节点数量（即当前层的大小），处理完这一层的所有节点后再递增字符，确保同一层使用相同的字符。
方向遍历：用二维数组存储上下左右四个方向，简化代码逻辑。
内存管理：补充了队列和room内存的释放，避免内存泄漏。

运行修改后的代码，就能得到期望的

基于ASCII的C语言递归泛洪填充：如何实现字符向外扩散填充？

核心思路 #

具体修改步骤 #

修改后的完整代码 #

关键代码解释 #

核心思路

具体修改步骤

修改后的完整代码

关键代码解释