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

您在一种方法中投入了太多的责任。您可以将洪水填充算法与岛屿编号算法结合起来。

我创建了这个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);
    }
}

如您所见，这是一个使用递归的简单算法。

其次，您只需创建一个方法，对所有可能的图 block 调用 fill 算法。如果您到达值为 1 的点，您就知道该岛尚未被其他国王占领:D。因此，您填写它并使用 counter id 向国王声明它。通常，人们使用特殊的 boolean 数组来防止填充算法进入无限循环。您通过开始从索引 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。接下来，您的计数器仅针对每一行进行更新。如果两个idlands从同一行开始(正如您在输出中看到的那样)，这会导致问题。