给定矩阵中最大孤岛的算法

Question

给定2×2矩阵,返回可能的不同岛尺寸

例如,应返回以下矩阵[5, 7].

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

这是一个相当简单的问题.我使用相同大小的布尔访问矩阵并以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

您的代码中有两个错误.

请参阅Mick对第一个错误的评论:

一个明显的问题dfsIsland()是至少for (int col = 0; col < cols; cols++)可能应该for (int col = 0; col < cols; col++)改为(甚至可能更好地使用common i和jrow/col索引).

第二个错误是你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;
    }

}

UPDATE

为了获得所需的[7, 4](原始问题)输出,电路板需要使用水平环绕,因此底线上的两个小岛成为一个更大的岛.

通过修改一行代码以使用%模运算符包围列索引可以轻松实现这一点:

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