1

我的任务是使用递归和 2D Ascii 图像在 Java 中编写洪水填充算法。我编写了代码，它运行良好，但我不确定我是否可以更简单地编写它，因为我使用了太多 if 语句来检查一些东西，比如当前点在哪里（边缘、角落或中间）。

这是代码：

public class AsciiShop {

public static void main(String[] args) {
    String[] img = new String[5];

    img[0] = "++++++#";
    img[1] = "+#+++##";
    img[2] = "###++#+";
    img[3] = "+#++#++";
    img[4] = "+####++";


    fill(img, 1, 2, '0');

}

public static void fill(String[] image, int x, int y, char c) {

    String[] finalImage = image;

    char startChar = finalImage[y].charAt(x);

    StringBuilder stringBuilder = new StringBuilder(finalImage[y]);
    stringBuilder.setCharAt(x, c);

    finalImage[y] = stringBuilder.toString();

    if(y>0&&x>0&&y<(finalImage.length-1)&&x<(finalImage[y].length()-1)) {
        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);
    } 
    else if(y==0&&x==0) {

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);

    }

    else if (y==0&&x==(finalImage[y].length()-1)) {
        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);
    }

    else if (y==finalImage.length&&x==(finalImage[y].length()-1)) {

        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

    }

    else if (y==finalImage.length&&x==0) {

        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);

    }

    else if (y==0&&x>0&&x<(finalImage[y].length()-1)){

        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);
    }

    else if (y==(finalImage.length-1)&&x>0&&x<(finalImage[y].length()-1)){
        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);
    }

    else if (x==0&&y>0&&y<(finalImage.length-1)) {


        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

        //Rechter Nachbar
        if(finalImage[y].charAt(x+1) == startChar)
            fill(finalImage, x+1, y, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);
    }
    else if (x==(finalImage[y].length()-1)&&y>0&&y<(finalImage.length-1)) {

        //Linker Nachbar
        if(finalImage[y].charAt(x-1) == startChar)
            fill(finalImage, x-1, y, c);

        //Nachbar oben
        if(finalImage[y-1].charAt(x) == startChar)
            fill(finalImage, x, y-1, c);

        //Nachbar unter
        if(finalImage[y+1].charAt(x) == startChar)
        fill(finalImage, x, y+1, c);
    }

    for (int i=0; i<finalImage.length; i++) {
        System.out.println(finalImage[i]);
    }

    System.out.println();

}
}
4

2 回答 2

2

为什么不将边界检查和“边界/已填充”检查结合起来并将它们移动到自己的方法中？

public class ImageFiller {
    protected String[] finalImage;    // init these in constructor
    protected int sizeX;
    protected int sizeY;
    protected char startChar;
    protected char fillChar;


    public void fill (int x, int y) {
        // ...
        visitNeighbor( x-1, y);
        visitNeighbor( x+1, y);
        visitNeighbor( x, y-1);
        visitNeighbor( x, y+1);
        // ...
    }

    protected void visitNeighbor (int x, int y) {
        if (x < 0 || x >= sizeX)
            return;
        if (y < 0 || y >= sizeY)
            return;
        if (finalImage[y].charAt(x) != startChar) {
            // Boundary or Already Filled.
            return;
        }
        // Recursive Fill;   
        //  -- or could use a queue, to avoid excessively deep recursion.
        fill( x, y);
    }
}
于 2013-11-02T00:50:38.380 回答
2

您可以遍历每个方向，然后将边界检查放在循环内。循环遍历方向的常用技术是保持大小相等的 dx 和 dy 数组，表示每个方向的 x 和 y 的变化。抱歉，我在 C 中更舒服，但这些语言的语法相似，所以希望它没问题。

char img[5][7], finalimg[5][7];
int h = 5, w = 7;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int numdir = 4;

void startfill(int y, int x, char c) { // Copy img into finalimg then fill
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            finalimg[i][j] = img[i][j];
        }
    }
    fill(y, x, c);
}

void fill(int y, int x, char c) {
    char startchar = finalimg[y][x];
    finalimg[y][x] = c;
    for (int i = 0; i < numdir; i++) {
        int newy = y + dy[i];
        int newx = x + dx[i];
        if (newy >= 0 && newy < h && newx >= 0 && newx < w && finalimg[newy][newx] == startchar) {
            fill(newy, newx, c);
        }
    }
}
于 2013-11-02T01:05:02.637 回答