Рекурсивный FloodFill в Java

Question

У меня есть задача написать алгоритм заполнения заливки в Java с помощью рекурсии и 2D-изображения Ascii. Я написал код, и он работает отлично, но я не уверен, могу ли я написать его проще, потому что я использовал слишком много операторов 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(); 

} 
} 

Answer 1

Почему бы не совместить границы проверки & «граничные/уже заполнены» чеки и переместить их в их собственный метод?

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); 
    } 
} 

Answer 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); 
     } 
    } 
}