leetcode 200. Number of Islands（岛屿的数量）

小咪咪 2022-12-03 09:17 169阅读 0赞

[https://leetcode.com/problems/number-of-islands/][https_leetcode.com_problems_number-of-islands]

### 一、问题描述 ###

给定一个二维数组，其元素均为'1'和'0'，分别代表陆地和水，现在要计算数组中岛屿的数量。

被水包围的就是岛屿，此外，数组的四条边界均被水包围。

PS：某司的校招机试也出了这道题，该题反过来求一块有水有陆地的地域中湖泊的数量，解法完全一样。

测试用例：

Input: grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    Output: 1
    
    
    Input: grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    Output: 3

### 二、代码实现 ###

总体思路是进行两层for循环遍历二维数组的所有元素，对于每个遍历到的元素，如果是'1'，将其置为'0'，并且将它上下左右相邻的S也置为'0'； 如果是'0'，直接continue跳过该元素。

class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            
            int res = 0;    // 计数器（岛屿的数量）
            for (int i=0; i < grid.length; i++) {
                for (int j=0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        dfs(i, j, grid);
                        res ++;
                    }
                }
            }
            return res;
        }
    
        private void dfs(int i, int j, char[][] grid) {
            grid[i][j] = '0';
            if (i-1 >= 0 && grid[i-1][j] == '1') {  // 上
                dfs(i-1, j, grid);
            }
            if (i+1 < grid.length && grid[i+1][j] == '1') { // 下
                dfs(i+1, j, grid);
            }
            if (j-1 >= 0 && grid[i][j-1] == '1') {  // 左
                dfs(i, j-1, grid);
            }
            if (j+1 < grid[0].length && grid[i][j+1] == '1') { // 右
                dfs(i, j+1, grid);
            }
        } 
    }

[https_leetcode.com_problems_number-of-islands]: https://leetcode.com/problems/number-of-islands/