java - 给定矩阵中最大岛的算法

Question

给定一个 2 X 2 矩阵，返回可能的不同岛屿大小

例如，下面的矩阵应该返回[5, 7]。

  1 0 0 0 1
  1 1 1 1 1
  0 0 0 0 0
  1 1 1 1 1

这是一个相当简单的问题。我正在使用相同大小的 boolean 访问矩阵并以 DFS 方式遍历矩阵。我已经在这里实现了。出于某种原因，我得到的输出为 [1]。我尝试调试，但我的思绪现在停止工作了。我想念一些我认为很愚蠢的东西。

public class IslandConnectedCell {

    public static void main(String[] args) {

        int[][] input = {
                {1,0,0,0,1},
                {1,1,1,1,1},
                {0,0,0,0,0},
                {1,1,0,1,1}
        };

        dfsIsland(input);

    }


    public static void dfsIsland(int[][] input) {
        int rows = input.length;
        int cols = input[0].length;
        List<Integer> countList = new ArrayList<>();

        boolean visited[][] = new boolean[rows][cols];

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; cols++) {
                if (input[row][col] == 1 && !visited[row][col]) {
                    int count = mark(row, col, input, visited, rows, cols, 0);
                    countList.add(count);
                }
            }
        }
        System.out.println(countList);

    }

    public static int mark(int row, int col, int[][] input, boolean[][] visited, int rows, int cols, int count) {

        if (row >= rows || row < 0 || col >= cols || col < 0) {
            return 0;
        }

        if (input[row][col] == 0 || visited[row][col]) {
            return 0;
        }

        visited[row][col] = true;
        count+=1;

        for (int i = row - 1; i <= row + 1; i++) {
            for (int j = col - 1; j <= col + 1; j++) {
                if (i != row || j != col) {
                    mark(i, j, input, visited, rows, cols, count);
                }
            }
        }
        return count;
    }

}

Answer 1

您的代码中有两个错误。

参见 comment by Mick对于第一个错误:

One obvious problem in dfsIsland() is at least that for (int col = 0; col < cols; cols++) should probably be for (int col = 0; col < cols; col++) instead (maybe even better to use the common i and j for the row/col indices).

第二个错误是您使用了 count在mark方法，最明显的是在递归调用中没有使用返回值。请记住，Java 是按值传递的。
提示:我建议您删除 count作为参数。

修复错误后，输出将是:

[7, 2, 2]

---

public class IslandConnectedCell {

    public static void main(String... args) {
        int[][] board = { {1,0,0,0,1},
                          {1,1,1,1,1},
                          {0,0,0,0,0},
                          {1,1,0,1,1} };
        System.out.println(new IslandConnectedCell(board).getIslandSizes());
    }

    private final int[][] board;
    private final int rows;
    private final int cols;

    public IslandConnectedCell(int[][] board) {
        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;
    }

    public List<Integer> getIslandSizes() {
        boolean visited[][] = new boolean[this.rows][this.cols];
        List<Integer> countList = new ArrayList<>();
        for (int row = 0; row < this.rows; row++)
            for (int col = 0; col < this.cols; col++)
                if (this.board[row][col] == 1 && ! visited[row][col])
                    countList.add(mark(row, col, visited));
        return countList;
    }

    private int mark(int row, int col, boolean[][] visited) {
        if (row >= this.rows || row < 0 || col >= this.cols || col < 0 || this.board[row][col] == 0 || visited[row][col])
            return 0;
        visited[row][col] = true;
        int count = 1;
        for (int r = -1; r <= 1; r++)
            for (int c = -1; c <= 1; c++)
                if (r != 0 || c != 0)
                    count += mark(row + r, col + c, visited);
        return count;
    }

}

---

更新

获得 [7, 4] 的期望输出( original question )，电路板需要使用水平环绕，因此底线上的两个小岛变成一个较大的岛。

这很容易通过修改一行代码来使用%环绕列索引来实现。模运算符:

count += mark(row + r, (col + c + this.cols) % this.cols, visited);