如何将递归reveal_tiles函数转换为迭代版本以避免栈溢出？

问题背景 #

你实现的递归reveal_tiles函数用于标记H*W矩阵中所有与起始位置连通的无物品瓷砖为已揭露，但当处理大面积连通区域时，递归调用次数过多会触发栈溢出。原递归逻辑是从起始位置@出发，遍历8个相邻方向，递归处理未揭露的无物品瓷砖。

核心思路 #

递归本质是利用程序调用栈存储待处理节点，我们可以手动实现一个栈结构（或队列）模拟这个过程：把待处理的瓷砖坐标存入栈中，循环取出处理并将符合条件的相邻坐标压入栈，直到栈为空。这种方式将递归的栈开销转移到堆内存（或可控区域），避免递归深度超限导致的溢出。

迭代版本实现（C语言） #

方案1：数组模拟栈（适合小网格） #

#include <stdlib.h>

typedef struct {
    int y;
    int x;
} Coord;

static void reveal_tiles(int start_y, int start_x) {
    // 起始位置有物品，直接返回
    if (has_item(start_y, start_x)) {
        return;
    }

    // 初始化栈，大小为网格总单元格数，确保能容纳所有可能坐标
    Coord stack[H * W];
    int top = -1;

    // 压入起始坐标
    stack[++top] = (Coord){start_y, start_x};

    while (top >= 0) {
        // 弹出栈顶坐标
        Coord curr = stack[top--];
        int y = curr.y;
        int x = curr.x;

        // 已揭露的瓷砖跳过，避免重复处理
        if (grid[y][x] == FLAG_REVEALED) {
            continue;
        }

        // 标记当前瓷砖为已揭露
        grid[y][x] = FLAG_REVEALED;

        // 遍历8个相邻方向，处理边界
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                int ny = y + dy;
                int nx = x + dx;
                // 检查坐标合法性、无物品且未揭露
                if (ny >= 0 && ny < H && nx >= 0 && nx < W) {
                    if (!has_item(ny, nx) && grid[ny][nx] != FLAG_REVEALED) {
                        stack[++top] = (Coord){ny, nx};
                    }
                }
            }
        }
    }
}

方案2：动态分配栈（适合大网格，避免局部数组溢出） #

如果网格尺寸较大（如1000×1000），局部数组可能耗尽函数栈空间，改用堆内存分配更安全：

#include <stdlib.h>

typedef struct {
    int y;
    int x;
} Coord;

static void reveal_tiles(int start_y, int start_x) {
    if (has_item(start_y, start_x)) {
        return;
    }

    // 动态分配栈内存
    Coord *stack = malloc(H * W * sizeof(Coord));
    if (!stack) {
        // 内存分配失败，可按需添加错误处理
        return;
    }
    int top = -1;

    stack[++top] = (Coord){start_y, start_x};

    while (top >= 0) {
        Coord curr = stack[top--];
        int y = curr.y;
        int x = curr.x;

        if (grid[y][x] == FLAG_REVEALED) {
            continue;
        }

        grid[y][x] = FLAG_REVEALED;

        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                int ny = y + dy;
                int nx = x + dx;
                if (ny >= 0 && ny < H && nx >= 0 && nx < W) {
                    if (!has_item(ny, nx) && grid[ny][nx] != FLAG_REVEALED) {
                        stack[++top] = (Coord){ny, nx};
                    }
                }
            }
        }
    }

    // 释放动态分配的内存
    free(stack);
}

关键细节说明 #

• 避免重复处理：每次弹出坐标后先检查是否已揭露，跳过已处理瓷砖，防止同一坐标多次入栈。
• 边界检查：遍历相邻方向时确保坐标在网格范围内，避免越界访问。
• 遍历顺序可选：栈模拟的是深度优先搜索（DFS），和原递归逻辑遍历顺序一致；若改用队列则是广度优先搜索（BFS），最终揭露结果完全相同，仅遍历顺序不同。

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