2013-11-02 91 views
1

我有任務使用遞歸和2D Ascii圖像在Java中編寫洪水填充算法。我寫了代碼,它完美的工作,但我不確定是否可以寫得更簡單,因爲我使用太多if語句來檢查某些內容,比如當前點(邊,角或中間)。Java中的遞歸填充

下面是代碼:

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

} 
} 
+6

這個問題似乎是題外話題,因爲它是關於代碼審查。 [codereview.se]可能更適合。 – Dukeling

回答

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

托馬斯,這是一個非常好的解決方案,但是當y = -1,x = -1或者當它們大於界限時有一個錯誤(例外)。另外我需要使用主要和填充方法。 – Hrvoje

+0

在'visitNeighbor()'的開頭就有x&y的警戒條件,所以提供的'fill()'在合理的初始位置被調用,這已經被明確地測試過了。 –

+1

此代碼是概要。在堆棧溢出時,期望自己完成工作,充實或修改代碼。你可以肯定地放入'main'方法,不是嗎? **因爲我的合同費率是每小時80美元。長話短說:SO不是作業或轉讓服務。 –

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

謝謝你的解決方案,但我需要圖像在字符串數組中。 – Hrvoje