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在同一行开始，这会导致问题（正如你可以看到你的输出一样）。