java - 如何启动桶填充算法

Question

我有一个任务，但我不知道如何开始。如果有人知道，请将一些帖子的链接发给我。我有一个最小的 Java 类，我需要在其中更新“fill”方法，以便它根据以下描述工作:

Pretend you are working in MS Paint, or a similar graphics application. Your job is to implement the bucket-fill tool. More specifically, given a two-dimensional grid, an (X,Y) position that the user clicked on, and a color, devise an algorithm that can be used to fill appropriate part of the grid.

The bucket-fill algorithm should 'paint' all pixels that are connected to the pixel that the user clicked on, all the way to the borders where the color changes. So for example, if the user clicks on a white pixel, and specifies the color green, the bucket-fill tool will turn all of the touching white pixels into green pixels. It will not, however, affect white pixels that are in a completely separate part of the image.

一个最小的 Java 类:

class BucketFill {

    private char[][] pixels;

    public BucketFill(char[][] pixels) {
        this.pixels = pixels;
    }

    public void fill(int x, int y, char color) {
        // TODO: make this method work
    }

    public void inspect() {
        for (int y = 0; y < pixels.length; y++) {
            for (int x = 0; x < pixels[y].length; x++) {
                System.out.print(pixels[y][x]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String argv[]) {
        char pixels[][] =
        {
            { 'O', 'X', 'X', 'X', 'X' },
            { 'X', 'O', 'O', 'O', 'X' },
            { 'X', 'O', '#', 'O', 'X' },
            { 'X', 'O', 'O', 'O', 'X' },
            { 'X', 'X', 'X', 'X', 'X' },
            { 'X', 'X', 'X', '#', '#' },
            { 'X', 'X', 'X', 'X', 'X' }
        };
        BucketFill bucketFill = new BucketFill(pixels);
        bucketFill.fill(0, 0, '*');
        bucketFill.fill(3, 0, 'O');
        bucketFill.fill(2, 1, '@');
        bucketFill.inspect();
    }
}

Answer 1

您可以使用洪水填充算法。 Flood Fill

您可以使用基于堆栈的递归来实现它。它只是递归地为连接的节点着色。