解决递归洪水填充算法中的栈溢出问题：原理与迭代优化

public class RecursiveFloodFill {

    private static boolean[][] went; // 用于标记已访问的坐标
    private static int[][] grid;     // 假设的网格数据，例如0表示空，1表示可填充

    // 初始化网格和访问数组（实际应用中应在外部进行）
    public static void init(int[][] initialGrid) {
        grid = initialGrid;
        went = new boolean[initialGrid.length][initialGrid[0].length];
    }

    public static int flood(int x, int y) {
        // 边界检查：确保坐标在有效范围内，且该点未被访问过
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || went[x][y]) {
            return 0;
        }

        // 标记当前点为已访问
        went[x][y] = true;
        // System.out.println("Visiting: " + x + ", " + y); // 调试输出

        // 如果当前点不符合填充条件（例如grid[x][y]不为1），则停止此路径的填充
        // 注意：此处逻辑应根据具体需求调整，例如如果grid[x][y] != targetColor就停止
        if (grid[x][y] != 1) { // 假设我们填充所有值为1的区域
            return 0;
        }

        int result = 1; // 当前点符合条件，计数为1

        // 递归调用，向四个相邻方向扩散
        result += flood(x + 1, y); // 右
        result += flood(x, y + 1); // 下
        result += flood(x - 1, y); // 左
        result += flood(x, y - 1); // 上

        return result;
    }

    public static void main(String[] args) {
        int[][] sampleGrid = {
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 0}
        };
        init(sampleGrid);
        int count = flood(1, 1); // 从(1,1)开始填充
        System.out.println("填充的单元格数量: " + count); // 预期输出 7

        // 尝试一个可能导致深层递归的场景（假设网格非常大，且路径很长）
        // 如果网格是100x100，从(0,0)一直到(99,99)的路径，将导致非常深的递归
        // 例如，如果从(0,0)开始，一直递归到(99,0)，再到(99,1)，以此类推
        // 每次递归调用都会在JVM调用栈上创建一个新的栈帧
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class IterativeFloodFill {

    private static int[][] grid;    // 假设的网格数据
    private static boolean[][] went; // 访问标记
    private static int R, C;        // 网格的行数和列数
    private static int targetValue; // 要填充的目标值

    // 辅助类：表示网格中的一个坐标点
    static class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // 初始化网格和访问数组
    public static void initGrid(int[][] initialGrid, int valueToFill) {
        grid = initialGrid;
        R = grid.length;
        C = grid[0].length;
        went = new boolean[R][C];
        targetValue = valueToFill;
    }

    /**
     * 执行迭代式洪水填充
     * @param startX 起始点的行坐标
     * @param startY 起始点的列坐标
     * @param fillColor 填充后的新值
     * @return 填充的单元格数量
     */
    public static int floodIterative(int startX, int startY, int fillColor) {
        // 边界检查：起始点是否有效，是否已访问
        if (startX < 0 || startX >= R || startY < 0 || startY >= C || went[startX][startY]) {
            return 0;
        }
        // 如果起始点不符合填充条件，直接返回
        if (grid[startX][startY] != targetValue) {
            return 0;
        }

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(startX, startY)); // 将起始点加入队列
        went[startX][startY] = true;             // 标记起始点已访问

        int filledCount = 0; // 记录填充的单元格数量

        // 定义四个方向的偏移量 (上, 下, 左, 右)
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Point current = queue.poll(); // 从队列中取出一个点
            // System.out.println("Processing: " + current.x + ", " + current.y); // 调试输出

            // 处理当前点：如果它符合填充条件，则计数并进行填充
            if (grid[current.x][current.y] == targetValue) {
                filledCount++;
                grid[current.x][current.y] = fillColor; // 将当前点的值修改为填充值
            }

            // 探索相邻节点
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                // 检查新坐标是否在网格内、是否未访问、是否符合填充条件（即与原始目标值相同）
                if (nx >= 0 && nx < R && ny >= 0 && ny < C && !went[nx][ny] && grid[nx][ny] == targetValue) {
                    went[nx][ny] = true; // 标记为已访问
                    queue.offer(new Point(nx, ny)); // 将符合条件的邻居加入队列
                }
            }
        }
        return filledCount;
    }

    public static void main(String[] args) {
        int[][] sampleGrid = {
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 0}
        };

        // 第一次填充：从(1,1)开始，填充值为1的区域，替换为9
        initGrid(sampleGrid, 1);
        int count1 = floodIterative(1, 1, 9);
        System.out.println("第一次填充的单元格数量: " + count1); // 预期输出 7
        System.out.println("填充后的网格 (第一次):