Flood Fill (洪水填充、泛洪填充、油漆桶)算法Java

什么是Flood Fill (洪水填充、泛洪填充、油漆桶算法)

从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。
因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。
详细解释： 维基百科Flood Fill

实现（油漆桶）四通实现

import java.util.LinkedList;

public class FloodFill {

    protected int[][] colors;   // 颜色池

    protected int x, y;         // 二维数组（图片）大小

    /* 记录点 */
    private final class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    /**
     * 设置二维数组（图片）
     * @param colors 二维数组，模拟图片每个点的颜色
     * @param x 图片x轴大小
     * @param y 图片y轴大小
     */
    public void setColors(int[][] colors, int x, int y) {
        this.colors = colors;
        this.x = x;
        this.y = y;
    }

    /**
     * floodFill(BFS)，选中坐标(cx,cy)必须为有效点
     *
     * @param cx       x 坐标
     * @param cy       y 坐标
     * @param newColor 新颜色
     */
    public final void floodFill(int cx, int cy, int newColor) {
        final LinkedList<Point> q = new LinkedList<>();
        q.offer(new Point(cx, cy));
        final int color = colors[cx][cy];
        colors[cx][cy] = newColor;
        while (!q.isEmpty()) {
            final Point inner = q.poll();
            int x = inner.x;
            int y = inner.y;
            x++;
            if (x < this.x && color == colors[x][y]) {
                colors[x][y] = newColor;
                q.offer(new Point(x, y));
            }
            x -= 2;
            if (x >= 0 && color == colors[x][y]) {
                colors[x][y] = newColor;
                q.offer(new Point(x, y));
            }
            x++;
            y++;
            if (y < this.y && color == colors[x][y]) {
                colors[x][y] = newColor;
                q.offer(new Point(x, y));
            }
            y -= 2;
            if (y >= 0 && color == colors[x][y]) {
                colors[x][y] = newColor;
                q.offer(new Point(x, y));
            }
        }
    }
}

测试（简单使用）

public static void main(String[] args) {
    int[][] colors = new int[][]{
            {0, 1, 2, 1, 1, 1},
            {2, 1, 4, 1, 2, 1},
            {3, 1, 1, 1, 5, 2},
            {5, 0, 1, 0, 1, 9},
            {5, 8, 2, 0, 1, 1},
            {5, 0, 8, 0, 7, 2}
    };
    FloodFill floodFill = new FloodFill();
    floodFill.setColors(colors, 6, 6);
    floodFill.floodFill(1, 1, 6);
    for (int[] c : colors) {
        for (int dot : c)
            System.out.print(dot + ", ");
        System.out.println();
    }
}
/*
******************************
*       测试结果
******************************
*   0, 6, 2, 6, 6, 6, 
*   2, 6, 4, 6, 2, 6, 
*   3, 6, 6, 6, 5, 2, 
*   5, 0, 6, 0, 1, 9, 
*   5, 8, 2, 0, 1, 1, 
*   5, 0, 8, 0, 7, 2,
******************************
*/