5
\$\begingroup\$

Doing homework, implementation of the algorithm flood fills. I'm writing a program to this guide: http://en.wikipedia.org/wiki/Flood_fill. And I have some questions:

  1. Is it normal to specify the parameters in function replaces the color of any character bucketFill.fill (0, 0, '*', 'O');, I do not know what kind of color will be initially to these coordinates?
  2. An algorithm is correct? I wrote it for example in Wikipedia, but the result of my program is as follows:

    @@@@@
    @@@@@
    @@@@@
    @@@@@
    @@@@@
    @@@@@
    @@@@@
    

    I think must be this:

    *@@@@
    @@@@@
    @@#@@
    @@@@@
    @@@@@
    @@@##
    @@@@@
    

My code:

class BucketFill {

    private char[][] pixels;

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

    public void fill(int x, int y, char newColor, char oldColor) {
        if (x < 0) return;
        if (y < 0) return;
        if (x >= pixels.length) return;
        if (y >= pixels[x].length) return;

        oldColor = pixels[x][y];

        if (newColor == pixels[x][y]) return;
        if (oldColor != pixels[x][y]) return;

        pixels[x][y] = newColor;

        fill(x - 1, y, newColor, oldColor);
        fill(x + 1, y, newColor, oldColor);
        fill(x, y - 1, newColor, oldColor);
        fill(x, y + 1, newColor, oldColor);
    }

    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, '*', 'O');
        bucketFill.fill(3, 0, 'O', 'O');
        bucketFill.fill(2, 1, '@', 'O');
        bucketFill.inspect();
    }
}
\$\endgroup\$
5
\$\begingroup\$
  1. Normally there's no need to specify the color to change from. You only need to specify the coordinates and leave it up to the flood fill routine to find out what color is at that location. I would define another method that is public, and make the recursive method a private implementation method. The public method would look up the color at the location and then call the private method.

    public void fill(int x, int y, char newColor) {
        fill(x, y, newColor, pixels[x][y]);
    }
    
    private void fill(int x, int y, char newColor, char oldColor) {
        ...
    }
    
  2. You are not using oldColor correctly; you're overwriting the parameter value. The line:

    oldColor = pixels[x][y];
    

    should either be deleted or (better) amended to:

    char color = pixels[x][y];
    

    And the lines:

    if (newColor == pixels[x][y]) return;
    if (oldColor != pixels[x][y]) return;
    

    should then be changed to use the color variable:

    if (newColor == color) return;
    if (oldColor != color) return;
    

    Other than that, you have implemented the algorithm correctly.

    It's worth noting that the way this algorithm uses recursion could lead to a stack overflow for a large block of color. Also, by dint of the +1 and -1, will end up calling fill() multiple times for each cell.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.