题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

解题思路

找到一个值为'1'的点（岛屿），把该点地值置为'1'，在它的周围（上下左右）继续（递归地）找值为'1'的点，同样，找到后就把该点的值置为'1'，直到找不到值为'1'的点，这样就完成了一座岛屿的搜索，计数器加一。

对二维数组中的每一个点执行上述操作，完成后返回计数器的值，即为岛屿的数量。

源代码

public int numIslands (char[][] grid) {
    int m = grid.length;
    if (m == 0) return 0;
    int n = grid[0].length;
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs (char[][] grid, int i, int j) {
    if (i >= 0 && j >= 0 
        && i < grid.length 
        && j < grid[0].length 
        && grid[i][j] == '1') {
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}