岛屿的个数

描述

给一个01矩阵,求不同的岛屿的个数。
0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例

在矩阵:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

中有 3 个岛.


考察点
  • 如何寻找附近点是否是岛屿
  • 如何判断是否查询过该岛屿
答案
public int numIslands(boolean[][] grid) {
    if (grid == null || grid.length == 0)
        return 0;
    int num = 0;
    int[][] visited = new int[grid.length][grid[0].length];
    int length = grid.length;
    int perlength = grid[0].length;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < perlength; j++) {
            if (visited[i][j] == 0 && grid[i][j]) {
                findLand(grid, visited, i, j, length, perlength);
                num += 1;
            }
        }
    }
    return num;
}

public void findLand(boolean[][] grid, int[][] visited, int i, int j, int length, int perlength) {
    if (i < 0 || i >= length || j < 0 || j >= perlength) {
        return;
    }
    if (visited[i][j] == 0) {
        visited[i][j] = 1;
        if (grid[i][j]) {
            findLand(grid, visited, i - 1, j, length, perlength);
            findLand(grid, visited, i + 1, j, length, perlength);
            findLand(grid, visited, i, j - 1, length, perlength);
            findLand(grid, visited, i, j + 1, length, perlength);
        }
    }
}