如何用非递归方式实现C语言二维数组八连通区域分组标记

你的代码核心问题是没有对连通区域进行完整的扩展遍历：只是一次性检查当前点的8个邻接点并标记，但没有把这些邻接点作为新的起点继续搜索它们的邻接点，导致每个1都被当成独立的区域，counter每次循环都递增，最终每个1的标记都不一样。

要解决非递归的八连通区域标记问题，我们可以用广度优先搜索（BFS）——用队列来存储待处理的坐标，每次取出一个点，遍历它的8个邻接，把符合条件（未标记、是1）的点加入队列并标记，直到队列空，这样就能完整覆盖整个连通区域。

#include <stdio.h>
#define L 5

// 存储坐标的结构体，用于队列
typedef struct {
    int x;
    int y;
} Point;

void printImgArray(int array[L][L]) {
    printf("------ Image Contents -------\n");
    int i, j;
    for (i = 0; i < L; i++) {
        for (j = 0; j < L; j++)
            printf("%02d, ", array[i][j]);
        printf("\n");
    }
    printf("-----------------------------\n");
}

// 检查坐标是否在数组范围内
int checkIndex(int i, int j) {
    return i >= 0 && j >= 0 && i < L && j < L;
}

int colorNonRecursively(int image[L][L]) {
    int copyArray[L][L] = {0}; // 标记是否已处理过
    int counter = 0;
    // 模拟队列：用数组存储Point，front和rear控制队列进出
    Point queue[L*L]; // 最多L*L个点，足够存储所有坐标
    int front = 0, rear = 0;

    // 遍历整个数组
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < L; j++) {
            // 如果当前点是1且未被处理，开始新的分组
            if (image[i][j] == 1 && !copyArray[i][j]) {
                counter++;
                // 将当前点加入队列，标记为已处理
                queue[rear++] = (Point){i, j};
                copyArray[i][j] = 1;
                image[i][j] = counter;

                // BFS遍历整个连通区域
                while (front < rear) {
                    Point curr = queue[front++];
                    // 遍历8个邻接方向
                    for (int dx = -1; dx <= 1; dx++) {
                        for (int dy = -1; dy <= 1; dy++) {
                            // 跳过当前点自身（dx=0且dy=0）
                            if (dx == 0 && dy == 0) continue;
                            int new_x = curr.x + dx;
                            int new_y = curr.y + dy;
                            // 检查坐标合法，且是未处理的1
                            if (checkIndex(new_x, new_y) && image[new_x][new_y] == 1 && !copyArray[new_x][new_y]) {
                                copyArray[new_x][new_y] = 1;
                                image[new_x][new_y] = counter;
                                queue[rear++] = (Point){new_x, new_y};
                            }
                        }
                    }
                }
            }
        }
    }
    return counter;
}

int main() {
    int cellImg[L][L] = {
        {0,0,1,1,0},
        {1,0,1,1,0},
        {1,0,0,1,1},
        {1,1,0,0,0},
        {1,0,0,1,1}
    };
    printImgArray(cellImg);
    int groupCount = colorNonRecursively(cellImg);
    printImgArray(cellImg);
    printf("Group count: %d\n", groupCount);
    return 0;
}

1. 引入队列实现BFS：用数组模拟队列存储待处理的坐标，确保每个连通区域的所有点都被遍历到，而不是只处理直接邻接点。
2. 分组逻辑调整：只有当遇到未处理的1时，才递增counter（代表新的分组），然后用BFS遍历整个连通区域，把所有连通的1都标记为当前counter值。
3. 跳过自身邻接：在遍历8个方向时，跳过dx=0且dy=0的情况（即当前点本身），避免重复处理。
4. 处理状态标记：用copyArray记录哪些点已经被处理，防止重复加入队列和标记。

运行修正后的代码，输出会和你预期的一致：

------ Image Contents -------
00, 00, 01, 01, 00, 
01, 00, 01, 01, 00, 
01, 00, 00, 01, 01, 
01, 01, 00, 00, 00, 
01, 00, 00, 01, 01, 
-----------------------------
------ Image Contents -------
00, 00, 02, 02, 00, 
01, 00, 02, 02, 00, 
01, 00, 00, 02, 02, 
01, 01, 00, 00, 00, 
01, 00, 00, 03, 03, 
-----------------------------
Group count: 3

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