Java遞歸問題與洪水填充算法

Question

我想編寫一個程序來定位和計算網格中的所有連接區域。連接區域由一組標記的單元格（值爲1）構成，使得該區域中的每個單元格可以通過向上，向下，向左或向右移動來自該區域中另一個標記的單元格，對角線上的單元格不被視爲連接。 所以，它將採取的輸入：

10 20 
0 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 
0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 
0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 
1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 
1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 
1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 
0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 0 
0 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 
0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 
1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 

和輸出：

0 1 1 0 0 0 2 0 3 3 0 0 0 0 4 0 0 0 5 0 
0 1 1 1 0 2 2 0 0 3 0 0 4 4 4 0 0 0 5 5 
0 0 1 0 0 0 2 2 0 3 0 0 0 4 0 0 0 5 5 5 
6 0 0 0 0 0 0 0 3 3 0 0 7 0 0 0 5 5 5 0 
6 6 0 6 0 0 0 3 3 3 0 0 0 8 8 0 5 5 0 0 
6 6 6 6 0 0 0 0 0 0 9 0 8 8 8 0 0 0 0 0 
0 6 6 6 0 0 0 9 9 9 9 0 0 8 8 0 8 0 0 0 
0 6 6 6 6 6 0 0 9 9 9 0 0 0 8 8 8 8 8 0 
0 0 0 6 6 0 0 0 0 9 0 0 0 8 8 0 0 8 8 0 
10 0 6 6 6 6 6 0 0 0 0 0 0 0 8 8 0 8 0 0 

現在，當我運行的代碼，我得到：

0 2 2 0 0 0 2 0 2 2 0 0 0 0 2 0 0 0 2 0 
0 3 3 3 0 3 3 0 0 3 0 0 3 3 3 0 0 0 3 3 
0 0 4 0 0 0 4 4 0 4 0 0 0 4 0 0 0 4 4 4 
5 0 0 0 0 0 0 0 5 5 0 0 5 0 0 0 5 5 5 0 
6 6 0 6 0 0 0 6 6 6 0 0 0 6 6 0 6 6 0 0 
7 7 7 7 0 0 0 0 0 0 7 0 7 7 7 0 0 0 0 0 
0 8 8 8 0 0 0 8 8 8 8 0 0 8 8 0 8 0 0 0 
0 9 9 9 9 9 0 0 9 9 9 0 0 0 9 9 9 9 9 0 
0 0 0 10 10 0 0 0 0 10 0 0 0 10 10 0 0 10 10 0 
11 0 11 11 11 11 11 0 0 0 0 0 0 0 11 11 0 11 0 0 

這裏是我的代碼：

package project2; 

import java.io.FileInputStream; 
import java.io.IOException; 
import java.util.Scanner; 

public class Project2 { 


    private static int height; 
    private static int length; 

    public static void main(String[] args) { 

     String inputFile; 

     Scanner input = new Scanner(System.in); 

     System.out.print("Enter input file name: "); 
     inputFile = "test_case_proj2.txt"; 

     try { 
      Integer grid[][] = loadGrid(inputFile); 

      System.out.println("Before flood fill"); 
      printGrid(grid); 

      findGroups(grid, 0, 0, 2, height, length); 

      System.out.println("After flood fill"); 
      printGrid(grid); 
     } catch (IOException e) { 
      System.err.println(e.getMessage()); 
     } 
    } 

    public static void findGroups(Integer[][] array, int column, int row, 
      int counter, int height, int length) { 
     for (int i = 0; i < height; i++) { 

      for (int j = 0; j < length; j++) { 

       if (row < 0 || row >= length || column < 0 || column >= height) { 
       } else { 
        if (array[column][j] == 1) { 
         array[column][j] = counter; 
         findGroups(array, column, row + 1, counter, height, length); 
         findGroups(array, column, row - 1, counter, height, length); 
         findGroups(array, column - row, j, counter, height, length); 
         findGroups(array, column + row, j, counter, height, length); 
        } 
       }  


      } 
      counter++; 
      column++; 
      row++; 
     } 
    } 

    public static Integer[][] loadGrid(String fileName) throws IOException { 

     FileInputStream fin; 

     fin = new FileInputStream(fileName); 

     Scanner input = new Scanner(fin); 

     height = input.nextInt(); 
     length = input.nextInt(); 

     Integer grid[][] = new Integer[height][length]; 

     for (int r = 0; r < height; r++) { 
      for (int c = 0; c < length; c++) { 
       grid[r][c] = input.nextInt(); 
      } 
     } 
     fin.close(); 

     return (grid); 
    } 

    public static void printGrid(Integer[][] grid) { 
     for (Integer[] grid1 : grid) { 
      for (int c = 0; c < grid[0].length; c++) { 
       System.out.printf("%3d", grid1[c]); 
      } 
      System.out.println(); 
     } 
    } 
} 

是否有人看看我做錯了什麼？

Answer 1

你把太多的責任放在一個方法中。您可以將floodfill算法與島編號算法結合使用。我創建了這個jdoodle。

首先你最好創建一個單獨的fill方法，它只不過是用一個計數器的值填充島嶼（我已經使它成爲靜態的，所以你不需要通過它的算法，儘管這是任意的）：

public static void fill(Integer[][] array, int column, int row, int height, int length) { 
    if (row >= 0 && row < length && column >= 0 && column < height && array[column][row] == 1) { 
     array[column][row] = counter; 
     fill(array, column, row + 1, height, length); 
     fill(array, column, row - 1, height, length); 
     fill(array, column - 1, row, height, length); 
     fill(array, column + 1, row, height, length); 
    } 
} 

正如您所看到的，它是一種使用遞歸的簡單算法。其次，您只需創建一個在所有可能的圖塊上調用fill算法的方法。如果你達到一個值爲1的點，你知道這個島還沒有被另一個國王所主張：D。這樣你就可以填寫它並向counter ID的國王聲明它。通常使用一個特殊的布爾數組來防止fill算法進入無限循環。你通過開始從指數counter = 2開始指定數字，巧妙地解決了這個問題，當然，一旦所有的島嶼都被要求，你需要減少數值。

public static void findGroups(Integer[][] array, int column, int row, int height, int length) { 
    for (int i = 0; i < height; i++) { 
     for (int j = 0; j < length; j++) { 
      if (array[i][j] == 1) { 
       fill(array, i,j, height, length); 
       counter++; 
      } 
     } 
    } 
    for (int i = 0; i < height; i++) { 
     for (int j = 0; j < length; j++) { 
      if (array[i][j] > 1) { 
       array[i][j]--; 
      } 
     } 
    } 
} 

算法的其餘部分保持不變（該算法現在從stdin讀取，但是這僅僅是爲了確保jdoodle繼續工作）。

---

關於你的算法，這很難理解。例如，您使用填充和部分呼叫使用column和row，其他部分使用j。接下來你的計數器只針對每一行進行更新。如果兩個idland在同一行開始，這會導致問題（正如你可以看到你的輸出一樣）。