每日算法 — 使用java实现Flood Fill：连通区域填充与泛洪搜索算法

引言

Flood Fill（泛洪填充） 是计算机图形学和游戏开发中最基础也最实用的算法之一。从 Windows 画图软件的”油漆桶”工具，到《扫雷》中点击空白格自动展开大片区域，再到《消消乐》中消除同色连通块，Flood Fill 无处不在。

本文将用 Java 完整实现 Flood Fill 算法，涵盖四连通/八连通两种模式、BFS 与 DFS 两种实现、以及实际游戏场景中的优化策略。

算法原理

什么是 Flood Fill？

Flood Fill 的核心任务：给定一个二维网格中的起始点，找到所有与起始点连通且颜色相同的区域，并对这些区域执行某种操作（如标记、填充、删除等）。

想象一滴墨水落在宣纸上，墨水会沿着纤维向四周扩散，直到遇到边界或不同颜色的区域——这就是 Flood Fill 的直观理解。

连通性定义

• 四连通（4-connected）：只考虑上、下、左、右四个方向
• 八连通（8-connected）：额外考虑四个对角线方向

选择哪种连通性取决于具体应用场景。例如图像处理通常用四连通，而围棋的气计算需要八连通。

Java 实现

1. 基础 DFS 递归实现

/**
 * Flood Fill基础实现 - DFS递归版本
 * 代码简洁但存在栈溢出风险，不适合大规模网格
 */
public class FloodFillDFS {

    // 四连通方向向量：上、右、下、左
    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    // 八连通方向向量（在需要时使用）
    private static final int[] DX8 = {-1, -1, -1, 0, 0, 1, 1, 1};
    private static final int[] DY8 = {-1, 0, 1, -1, 1, -1, 0, 1};

    /**
     * 基础DFS Flood Fill
     * @param grid 二维网格，元素表示颜色/类型
     * @param startRow 起始行
     * @param startCol 起始列
     * @param newColor 要填充的新颜色
     * @return 被填充的格子数量
     */
    public int fill(int[][] grid, int startRow, int startCol, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        // 边界检查
        if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
            return 0;
        }

        int targetColor = grid[startRow][startCol];

        // 如果新颜色与目标颜色相同，无需操作
        if (targetColor == newColor) {
            return 0;
        }

        return dfs(grid, startRow, startCol, targetColor, newColor);
    }

    private int dfs(int[][] grid, int row, int col, int targetColor, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        // 边界检查 + 颜色匹配检查
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return 0;
        }
        if (grid[row][col] != targetColor) {
            return 0;
        }

        // 填充当前格子
        grid[row][col] = newColor;
        int count = 1;

        // 递归探索四个方向
        for (int i = 0; i < 4; i++) {
            count += dfs(grid, row + DX[i], col + DY[i], targetColor, newColor);
        }

        return count;
    }

    /**
     * 八连通版本
     */
    public int fill8Connected(int[][] grid, int startRow, int startCol, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
            return 0;
        }

        int targetColor = grid[startRow][startCol];
        if (targetColor == newColor) return 0;

        return dfs8(grid, startRow, startCol, targetColor, newColor);
    }

    private int dfs8(int[][] grid, int row, int col, int targetColor, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (row < 0 || row >= rows || col < 0 || col >= cols) return 0;
        if (grid[row][col] != targetColor) return 0;

        grid[row][col] = newColor;
        int count = 1;

        for (int i = 0; i < 8; i++) {
            count += dfs8(grid, row + DX8[i], col + DY8[i], targetColor, newColor);
        }
        return count;
    }
}

2. BFS 队列实现（推荐）

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * Flood Fill BFS实现
 * 避免递归栈溢出，适合大规模网格
 */
public class FloodFillBFS {

    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    /**
     * BFS版本Flood Fill
     * 使用队列替代递归，空间复杂度O(min(R*C, 边界长度))
     */
    public int fill(int[][] grid, int startRow, int startCol, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
            return 0;
        }

        int targetColor = grid[startRow][startCol];
        if (targetColor == newColor) {
            return 0;
        }

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startRow, startCol});
        grid[startRow][startCol] = newColor;
        int count = 1;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];

            for (int i = 0; i < 4; i++) {
                int newRow = row + DX[i];
                int newCol = col + DY[i];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                        && grid[newRow][newCol] == targetColor) {
                    grid[newRow][newCol] = newColor;
                    queue.offer(new int[]{newRow, newCol});
                    count++;
                }
            }
        }

        return count;
    }

    /**
     * 优化的扫描线BFS（Scanline Flood Fill）
     * 大幅减少入队次数，适合图像填充等大面积区域
     */
    public int scanlineFill(int[][] grid, int startRow, int startCol, int newColor) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
            return 0;
        }

        int targetColor = grid[startRow][startCol];
        if (targetColor == newColor) return 0;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startRow, startCol, startCol}); // {row, left, right}

        // 先处理起始行
        int left = startCol;
        while (left > 0 && grid[startRow][left - 1] == targetColor) left--;
        int right = startCol;
        while (right < cols - 1 && grid[startRow][right + 1] == targetColor) right++;

        for (int c = left; c <= right; c++) {
            grid[startRow][c] = newColor;
        }

        int count = right - left + 1;

        while (!queue.isEmpty()) {
            int[] segment = queue.poll();
            int row = segment[0];
            int segLeft = segment[1];
            int segRight = segment[2];

            // 检查上下两行
            for (int dr : new int[]{-1, 1}) {
                int newRow = row + dr;
                if (newRow < 0 || newRow >= rows) continue;

                int c = segLeft;
                while (c <= segRight) {
                    // 跳过已填充或非目标颜色的格子
                    while (c <= segRight && grid[newRow][c] != targetColor) {
                        c++;
                    }
                    if (c > segRight) break;

                    // 找到一段连续的目标颜色
                    int segL = c;
                    while (c <= segRight && grid[newRow][c] == targetColor) {
                        grid[newRow][c] = newColor;
                        c++;
                    }
                    int segR = c - 1;
                    count += segR - segL + 1;
                    queue.offer(new int[]{newRow, segL, segR});
                }
            }
        }

        return count;
    }
}

3. 带访问标记的通用实现

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 通用Flood Fill实现
 * 支持自定义匹配条件和回调操作
 * 适用于复杂游戏逻辑（如消消乐、地图探索）
 */
public class GenericFloodFill {

    /**
     * 格子匹配接口：定义什么样的格子被视为"连通"
     */
    @FunctionalInterface
    public interface Matcher {
        boolean match(int row, int col, int value);
    }

    /**
     * 格子操作接口：定义对匹配格子执行的操作
     */
    @FunctionalInterface
    public interface CellProcessor {
        void process(int row, int col, int value);
    }

    /**
     * 泛洪填充核心方法
     * @param grid 二维网格
     * @param startRow 起始行
     * @param startCol 起始列
     * @param matcher 匹配条件
     * @param processor 处理操作
     * @return 连通区域的所有格子坐标
     */
    public java.util.List<int[]> flood(int[][] grid, int startRow, int startCol,
                                       Matcher matcher, CellProcessor processor) {
        int rows = grid.length;
        int cols = grid[0].length;
        java.util.List<int[]> region = new java.util.ArrayList<>();

        if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
            return region;
        }

        if (!matcher.match(startRow, startCol, grid[startRow][startCol])) {
            return region;
        }

        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];

            region.add(new int[]{row, col});
            if (processor != null) {
                processor.process(row, col, grid[row][col]);
            }

            for (int i = 0; i < 4; i++) {
                int nr = row + dx[i];
                int nc = col + dy[i];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc]
                        && matcher.match(nr, nc, grid[nr][nc])) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return region;
    }

    /**
     * 便捷方法：填充相同颜色的连通区域
     */
    public java.util.List<int[]> fillColor(int[][] grid, int startRow, int startCol, int newColor) {
        int targetColor = grid[startRow][startCol];
        return flood(grid, startRow, startCol,
            (r, c, val) -> val == targetColor,
            (r, c, val) -> grid[r][c] = newColor
        );
    }

    /**
     * 便捷方法：标记连通区域（不修改原网格）
     */
    public java.util.List<int[]> findRegion(int[][] grid, int startRow, int startCol) {
        int targetColor = grid[startRow][startCol];
        return flood(grid, startRow, startCol,
            (r, c, val) -> val == targetColor,
            null
        );
    }
}

4. 实战案例：消消乐连通块检测

import java.util.*;

/**
 * 消消乐（Match-3）游戏中的Flood Fill应用
 * 检测并消除三个以上连通的颜色块
 */
public class Match3Game {

    private static final int ROWS = 8;
    private static final int COLS = 8;
    private static final int EMPTY = 0;
    private static final int COLORS = 5; // 红、黄、蓝、绿、紫

    private final int[][] board;
    private final Random random;

    public Match3Game() {
        this.board = new int[ROWS][COLS];
        this.random = new Random();
        initializeBoard();
    }

    private void initializeBoard() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                board[r][c] = random.nextInt(COLORS) + 1;
            }
        }
        // 确保初始局面没有预先形成的匹配
        removeInitialMatches();
    }

    private void removeInitialMatches() {
        // 简化处理：重新随机直到无匹配
        while (findAllMatches().size() > 0) {
            for (int r = 0; r < ROWS; r++) {
                for (int c = 0; c < COLS; c++) {
                    board[r][c] = random.nextInt(COLORS) + 1;
                }
            }
        }
    }

    /**
     * 查找所有满足消除条件的连通块（大小>=3）
     */
    public List<List<int[]>> findAllMatches() {
        List<List<int[]>> allMatches = new ArrayList<>();
        boolean[][] visited = new boolean[ROWS][COLS];

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (visited[r][c] || board[r][c] == EMPTY) continue;

                List<int[]> region = findConnectedRegion(r, c, visited);
                if (region.size() >= 3) {
                    allMatches.add(region);
                }
            }
        }

        return allMatches;
    }

    /**
     * 使用Flood Fill查找与指定格子颜色相同的连通区域
     */
    private List<int[]> findConnectedRegion(int startRow, int startCol, boolean[][] visited) {
        List<int[]> region = new ArrayList<>();
        int color = board[startRow][startCol];

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            region.add(curr);

            for (int i = 0; i < 4; i++) {
                int nr = curr[0] + dx[i];
                int nc = curr[1] + dy[i];

                if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS
                        && !visited[nr][nc] && board[nr][nc] == color) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return region;
    }

    /**
     * 消除连通块并触发重力下落
     */
    public int eliminateMatches() {
        List<List<int[]>> matches = findAllMatches();
        int totalScore = 0;

        for (List<int[]> match : matches) {
            // 分数计算：基础分10分，每多一个额外加5分
            totalScore += 10 + (match.size() - 3) * 5;

            // 标记为空
            for (int[] cell : match) {
                board[cell[0]][cell[1]] = EMPTY;
            }
        }

        // 重力下落：每列中空位上方的方块下落
        applyGravity();

        // 填充新方块
        fillNewBlocks();

        return totalScore;
    }

    /**
     * 应用重力：每一列的非空方块下落到最底部
     */
    private void applyGravity() {
        for (int c = 0; c < COLS; c++) {
            int writeRow = ROWS - 1;
            for (int r = ROWS - 1; r >= 0; r--) {
                if (board[r][c] != EMPTY) {
                    board[writeRow][c] = board[r][c];
                    if (writeRow != r) {
                        board[r][c] = EMPTY;
                    }
                    writeRow--;
                }
            }
        }
    }

    private void fillNewBlocks() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (board[r][c] == EMPTY) {
                    board[r][c] = random.nextInt(COLORS) + 1;
                }
            }
        }
    }

    public void printBoard() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                System.out.printf("%2d ", board[r][c]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Match3Game game = new Match3Game();
        System.out.println("Initial board:");
        game.printBoard();

        // 模拟几次消除
        for (int i = 0; i < 3; i++) {
            int score = game.eliminateMatches();
            System.out.println("\nAfter elimination " + (i + 1) + ", score: " + score);
            game.printBoard();
        }
    }
}

复杂度分析

其中 R、C 分别为网格的行数和列数，α 为阿克曼函数的反函数（近似常数）。

进阶优化

1. 并查集预处理（离线查询）

当需要频繁查询不同位置的连通性时，可预先使用并查集（Union-Find）建立连通分量：

/**
 * 使用并查集预处理连通分量
 * 支持O(α)时间的连通性查询
 */
public class FloodFillUnionFind {
    private int[] parent;
    private int[] rank;

    public void preprocess(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        parent = new int[rows * cols];
        rank = new int[rows * cols];

        for (int i = 0; i < parent.length; i++) parent[i] = i;

        int[] dx = {-1, 0};
        int[] dy = {0, -1};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                for (int i = 0; i < 2; i++) {
                    int nr = r + dx[i];
                    int nc = c + dy[i];
                    if (nr >= 0 && nc >= 0 && grid[r][c] == grid[nr][nc]) {
                        union(r * cols + c, nr * cols + nc);
                    }
                }
            }
        }
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
    }

    public boolean isConnected(int r1, int c1, int r2, int c2, int cols) {
        return find(r1 * cols + c1) == find(r2 * cols + c2);
    }
}

2. 双向BFS（迷宫求解）

在寻找从起点到目标点的最短路径时，可从两端同时进行 Flood Fill：

public boolean bidirectionalSearch(int[][] grid, int[] start, int[] end) {
    // 同时从起点和终点扩散，相遇即找到路径
    Queue<int[]> queueStart = new ArrayDeque<>();
    Queue<int[]> queueEnd = new ArrayDeque<>();
    // ... 实现细节省略
    return false;
}

总结

Flood Fill 算法以其简洁高效的特点，成为处理二维网格连通性问题的首选方案。本文通过 Java 实现展示了：

1. DFS 递归：代码最简洁，但受栈深度限制
2. BFS 队列：避免栈溢出，适合生产环境
3. 扫描线优化：减少入队次数，提升大面积填充效率
4. 泛型抽象：支持自定义匹配条件和回调操作
5. 实战应用：消消乐连通块检测与消除的完整实现

在游戏开发中，Flood Fill 的变体随处可见——从《扫雷》的空白展开到《俄罗斯方块》的满行检测，从《围棋》的气计算到《塞尔达传说》的地图区域划分。掌握这一基础算法，是进军游戏开发的必备技能。