深度解析递归洪水填充的栈溢出问题与迭代优化

public class FloodFillRecursive {
    private static boolean[][] went; // 记录是否已访问
    private static int[][] grid;     // 模拟的网格，1表示可填充区域

    // 假设grid和went已初始化，例如：
    // grid = new int[102][102];
    // went = new boolean[102][102];

    /**
     * 执行洪水填充操作。
     * @param x 当前点的x坐标
     * @param y 当前点的y坐标
     * @return 如果当前点是可填充区域（grid[x][y] == 1），则返回1，否则返回0。
     */
    public static int flood(int x, int y) {
        // 边界检查：如果超出网格范围或已访问过，则直接返回
        if (x < 0 || y < 0 || x > 101 || y > 101 || went[x][y]) {
            return 0;
        }

        // 标记当前点为已访问
        went[x][y] = true;

        // 如果当前点不是目标区域，则直接返回0
        if (grid[x][y] == 1) { // 假设1是需要填充的区域
            return 1;
        }

        int result = 0;
        // 递归访问相邻的四个方向
        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) {
        // 示例初始化 (假设一个简单的10x10网格，边界为101)
        grid = new int[102][102];
        went = new boolean[102][102];

        // 填充部分区域为1，模拟可填充区域
        for (int i = 1; i <= 10; i++) {
            for (int j = 1; j <= 10; j++) {
                grid[i][j] = 0; // 假设0是可填充的
            }
        }
        // 示例：从(0,0)开始填充
        // 注意：在实际应用中，grid[x][y] == 1的条件通常是判断是否为需要改变颜色的目标像素
        // 这里为了演示栈溢出，假设flood方法内部的grid[x][y] == 1是退出条件
        // 实际的洪水填充通常是当grid[x][y] == 目标颜色时才继续递归
        // 这里的代码逻辑可能需要根据具体需求调整，但其递归深度问题是普遍存在的。
        // 例如，如果grid[x][y] == 0 且我们想填充所有0的区域，那么`if (grid[x][y] == 1) return 1;` 应该改为 `if (grid[x][y] != 0) return 0;`
        // 核心问题在于递归深度，而非具体逻辑。
        System.out.println("Starting flood fill...");
        // 模拟一个深路径，例如从(0,0)开始，一直向右或向下延伸
        // 这将导致深度优先的探索
        // 如果grid[x][y] == 1是退出条件，那么如果grid中没有1，它会一直探索到边界。
        // 为了复现栈溢出，我们假设grid大部分区域都是0，且从(0,0)开始，`if (grid[x][y] == 1)` 
        // 实际上是 `if (grid[x][y] != targetColor)` 或者 `if (grid[x][y] == boundaryColor)`
        // 这里为了简化，我们使用原问题中的代码结构，并假设grid中大部分区域不会立即触发 `return 1`。
        // 如果从(0,0)开始，且grid[0][0]不是1，它会继续调用 flood(1,0), flood(0,1)等
        // 假设grid大部分区域为0，且目标是找到1。如果从0,0开始，它会沿着0一直走，直到碰到边界或1。
        // 这里的关键是：即使不会回到相同坐标，一个深度优先的探索路径依然可能非常长。
        // 为了模拟栈溢出，我们假设grid中大部分区域为0，且从(0,0)开始，它会深度探索。
        // 例如，如果grid[0][0]到grid[100][0]都是0，它会一直递归下去。
        // 简化示例，假设从(0,0)开始，且大部分区域不会立即返回
        // 实际测试时，可以构造一个长条形的连通区域来触发栈溢出。
        // 例如，将grid[i][0]设置为0，i从0到100，然后从flood(0,0)开始。
        // 或者，将grid[i][j]全部设置为0，从flood(0,0)开始，它会探索整个102x102的网格。
        // 此时，如果`if (grid[x][y] == 1) return 1;` 永远不满足，则会一直递归到边界。
        // 这会导致非常深的递归。
        // 假设我们从(0,0)开始，且grid[x][y]大部分为0，`if (grid[x][y] == 1)` 永远不会触发。
        // 那么函数会一直递归到边界。
        // 例如，flood(0,0) -> flood(1,0) -> flood(2,0) -> ... -> flood(101,0)
        // 这种情况下，递归深度可达102层，这在默认JVM栈大小下可能导致栈溢出。
        // 如果考虑四个方向的探索，实际的深度会更快地增长。
        // 假设一个简单的场景，从(0,0)开始，如果所有相邻点都是可访问的，它会优先走一个方向，
        // 比如一直向右，直到边界，然后回溯，再走其他方向。
        // flood(0,0) -> flood(1,0) -> flood(2,0) -> ... -> flood(101,0)
        // 在到达flood(101,0)之前，大约会有102个方法调用堆叠在JVM的调用栈中。
        // 随后，flood(101,0)返回后，会尝试flood(100,1)等。
        // 整个网格的探索可能会导致非常深的调用链。
        try {
            flood(0, 0); // 从(0,0)开始填充
        } catch (StackOverflowError e) {
            System.err.println("发生栈溢出错误: " + e.getMessage());
            System.err.println("请尝试使用迭代方法或增加JVM栈大小。");
        }
    }
}

import java.awt.Point; // 引入Point类来表示坐标
import java.util.LinkedList;
import java.util.Queue;

public class FloodFillIterativeBFS {
    private static boolean[][] went; // 记录是否已访问
    private static int[][] grid;     // 模拟的网格，0表示可填充区域，1表示边界或已填充
    private static int R = 102;      // 行数
    private static int C = 102;      // 列数

    // 方向数组：上、下、左、右
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    /**
     * 执行迭代洪水填充操作。
     * @param startX 起始点的x坐标
     * @param startY 起始点的y坐标
     * @param targetColor 目标颜色（待填充区域的原始颜色）
     * @param fillColor 填充后的颜色
     */
    public static void floodFill(int startX, int startY, int targetColor, int fillColor) {
        // 初始化网格和访问数组
        grid = new int[R][C];
        went = new boolean[R][C];

        // 示例：初始化一个简单的网格，模拟大部分区域为targetColor
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                grid[i][j] = targetColor; // 假设所有都是目标颜色
            }
        }
        // 设置一个边界，例如grid[50][50] = 1 (非targetColor)
        grid[50][50] = 1;


        // 检查起始点是否合法且需要填充
        if (startX < 0 || startX >= R || startY < 0 || startY >= C || grid[startX][startY] != targetColor) {
            System.out.println("起始点无效或无需填充。");
            return;
        }

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

        int count = 0; // 记录填充了多少个点

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            int x = current.x;
            int y = current.y;

            grid[x][y] = fillColor; // 填充当前点
            count++;

            // 遍历四个相邻点
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];

                // 检查相邻点是否在网格内、未访问过且颜色是目标颜色
                if (newX >= 0 && newX < R && newY >= 0 && newY < C &&
                    !went[newX][newY] && grid[newX][newY] == targetColor) {

                    went[newX][newY] = true; // 标记为已访问
                    queue.offer(new Point(newX, newY)); // 加入队列
                }
            }
        }
        System.out.println("洪水填充完成，共填充 " + count + " 个点。");
    }

    public static void main(String[] args) {
        System.out.println("Starting iterative flood fill (BFS)...");
        // 从(0,0)开始，将所有0填充为2
        floodFill(0, 0, 0, 2); 
    }
}

java -Xss4m YourProgram