使用Floodfill填充ASCII圖像

Question

您好我想用Floodfill-alg填充ASCII圖像。我總是收到錯誤消息，我不知道爲什麼。

這是我的主要方法與輸入圖像：

public static void main(String[] args){ 
    Scanner sc = new Scanner("read 12\n+++++++++++++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#++\n++++++++++#--\nfill 2 2 d"); 
    String read, numberst; 
    String [] image; 
    int number = 0, count = 0; 
    Boolean error = false; 

    read = sc.next(); 
    numberst = sc.next(); 

    if ((read + numberst).matches("read[0-9]+")) { 
     number = Integer.parseInt(numberst); 
    } else { 
     error = true; 
    } 

    image = new String[number]; 

    System.out.println("image"); 

    while (sc.hasNextLine() && (error == false) && (count <= number - 1)) { 
     image[count] = sc.next(); 
     //System.out.println(image[count] + " " + count); 
     count++; 
     if (image[0].length() != image[count - 1].length()) { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 
    } 

    System.out.println("fill"); 
    while(sc.hasNextLine() && (error == false) && sc.hasNext()) { 
     String fill = "", xstr = "", ystr = "", cstr; 

     fill = sc.next(); 

     if (sc.hasNext()) { 
      xstr = sc.next(); 
     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 

     if (sc.hasNext() && error == false){ 
      ystr = sc.next(); 
     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 

     if (sc.hasNext() && error == false){ 
      cstr = sc.next(); 

      if ((fill + xstr + ystr + cstr).matches("fill[0-9]+[0-9]+.")) { 
      int x = Integer.parseInt(xstr), y = Integer.parseInt(ystr); 
      char c = cstr.charAt(0); 

      if (x <= image[0].length() && y <= number) { 
       fill(image, x, y, c); 
      } else { 
       error = true; 
       System.out.println("OPERATION FAILED"); 
      } 
      //System.out.println(fill + x + y + c); 
     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 

     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 
     //System.out.println(error); 
    } 

    if (error == false) { 
     for (int i = 0; i < number; ++i) { 
     System.out.println(image[i]); 
     } 
    } 
} 

這裏是我的填充方法的代碼：

public static void fill(String[] image, int x, int y, char c) { 
    char old = (image[y]).charAt(x); 
    Boolean r, l, o, u; 

    image[y] = (image[y]).substring(0, x) + c + (image[y]).substring(x + 1); 


    if ((x + 1) < image[0].length()) { 
     r = (image[y].charAt(x + 1) == old); 
    } else { 
     r = false; 
    } 
    if ((x - 1) >= 0) { 
     l = (image[y].charAt(x - 1) == old); 
    }else { 
     l = false; 
    } 
    if ((y - 1) >= 0) { 
     o = (image[y - 1].charAt(x) == old); 
    } else { 
     o = false; 
    } 
    if ((y + 1) <= image.length) { 
     u = (image[y + 1].charAt(x) == old); 
    } else { 
     u = false; 
    } 


    if (r == true) { 
     fill(image, x + 1, y, c); //According to the Error message it looks like the Java Compiler switches between this and... 
    } 
    if (l == true) { 
     fill(image, x - 1, y, c); //this line. 
    } 
    if (o == true) { 
     fill(image, x, y - 1, c); 
    } 
    if (u == true) { 
     fill(image, x, y + 1, c); 
    } 


} 

錯誤消息：

at AsciiShop.fill(AsciiShop.java:122) 
    at AsciiShop.fill(AsciiShop.java:119) 
    at AsciiShop.fill(AsciiShop.java:122) 
    at AsciiShop.fill(AsciiShop.java:119) 
    at AsciiShop.fill(AsciiShop.java:122) 
    at AsciiShop.fill(AsciiShop.java:119) 
    at AsciiShop.fill(AsciiShop.java:122) 
    at AsciiShop.fill(AsciiShop.java:119) 
    at AsciiShop.fill(AsciiShop.java:122) 

我沒有理念爲什麼這不起作用。 我希望你能幫助我。

Answer 1

起初你做的FloodFill錯了：在繼續之前，你應該檢查是否繼續沿着方向右邊;您首先檢查全部方向，然後繼續進行。這導致處理已經被替換的位置導致無限循環。 在if ((y + 1) <= image.length)有一個輸入錯誤 - 應該有嚴格的<。

您fill方法最小的變化將是：

public static void fill(String[] image, int x, int y, char c) { 
    char old = (image[y]).charAt(x); 

    image[y] = (image[y]).substring(0, x) + c + (image[y]).substring(x + 1); 

    if ((x + 1) < image[0].length() && 
      image[y].charAt(x + 1) == old) { 
     fill(image, x + 1, y, c); 
    } 

    if ((x - 1) >= 0 && 
      image[y].charAt(x - 1) == old) { 
     fill(image, x - 1, y, c); 
    } 

    if ((y - 1) >= 0 && 
      image[y - 1].charAt(x) == old) { 
     fill(image, x, y - 1, c); 
    } 

    if ((y + 1) < image.length && 
      image[y + 1].charAt(x) == old) { 
     fill(image, x, y + 1, c); 
    } 
} 

但是還是我建議實行FloodFill更「標準」的方式（見http://en.wikipedia.org/wiki/Flood_fill）與傳遞替換顏色，並檢查它明確了每個處理過的節點 - 它使代碼更加健壯和清晰。

見例（你main方法離開幾乎完好無損，fill重寫）：

public static void main(String[] args) { 
    Scanner sc = new Scanner(
      "read 12\n" 
      + "+++++++++++++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#++\n" 
      + "++++++++++#--\n" 
      + "fill 2 2 d"); 
    String read, numberst; 
    String[] image; 
    int number = 0, count = 0; 
    Boolean error = false; 

    read = sc.next(); 
    numberst = sc.next(); 

    if ((read + numberst).matches("read[0-9]+")) { 
     number = Integer.parseInt(numberst); 
    } else { 
     error = true; 
    } 

    image = new String[number]; 

    System.out.println("image"); 

    while (sc.hasNextLine() && (error == false) && (count <= number - 1)) { 
     image[count] = sc.next(); 
     // System.out.println(image[count] + " " + count); 
     count++; 
     if (image[0].length() != image[count - 1].length()) { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 
    } 

    System.out.println("fill"); 
    while (sc.hasNextLine() && (error == false) && sc.hasNext()) { 
     String fill = "", xstr = "", ystr = "", cstr; 

     fill = sc.next(); 

     if (sc.hasNext()) { 
      xstr = sc.next(); 
     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 

     if (sc.hasNext() && error == false) { 
      ystr = sc.next(); 
     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 

     if (sc.hasNext() && error == false) { 
      cstr = sc.next(); 

      if ((fill + xstr + ystr + cstr).matches("fill[0-9]+[0-9]+.")) { 
       int x = Integer.parseInt(xstr), y = Integer.parseInt(ystr); 
       char c = cstr.charAt(0); 

       if (x <= image[0].length() && y <= number) { 
        fill(image, x, y, image[y].charAt(x), c); 
       } else { 
        error = true; 
        System.out.println("OPERATION FAILED"); 
       } 
       // System.out.println(fill + x + y + c); 
      } else { 
       error = true; 
       System.out.println("INPUT MISMATCH"); 
      } 

     } else { 
      error = true; 
      System.out.println("INPUT MISMATCH"); 
     } 
     // System.out.println(error); 
    } 

    if (error == false) { 
     for (int i = 0; i < number; ++i) { 
      System.out.println(image[i]); 
     } 
    } 
} 

public static void fill(final String[] image, final int x, final int y, final char oldValue, final char newValue) { 
    if (oldValue == image[y].charAt(x)) { 
     image[y] = image[y].substring(0, x) + newValue + image[y].substring(x + 1); 

     if ((x + 1) < image[y].length()) { 
      fill(image, x + 1, y, oldValue, newValue); 
     } 

     if ((x - 1) >= 0) { 
      fill(image, x - 1, y, oldValue, newValue); 
     } 

     if ((y - 1) >= 0) { 
      fill(image, x, y - 1, oldValue, newValue); 
     } 

     if ((y + 1) < image.length) { 
      fill(image, x, y + 1, oldValue, newValue); 
     } 
    } 
}