给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:

[

[‘1’,’1’,’1’,’1’,’0’],

[‘1’,’1’,’0’,’1’,’0’],

[‘1’,’1’,’0’,’0’,’0’],

[‘0’,’0’,’0’,’0’,’0’]

]

输出: 1

示例 2:

输入:

[

[‘1’,’1’,’0’,’0’,’0’],

[‘1’,’1’,’0’,’0’,’0’],

[‘0’,’0’,’1’,’0’,’0’],

[‘0’,’0’,’0’,’1’,’1’]

]

输出: 3

解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/number-of-islands

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.         if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
  4.         boolean[][] record = new boolean[grid.length][grid[0].length];
  5.         int result = 0;
  6.         for(int i = 0; i < grid.length; i++){
  7.             for(int j = 0; j < grid[0].length; j++){
  8.                 result += flow(record,grid,i,j);
  9.             }
  10.         }
  11.         return result;
  12.     }
  14.     public int flow(boolean[][] record, char[][] grid, int row, int column){
  15.         if(row < 0 || row == grid.length || column < 0 || column == grid[0].length  || grid[row][column] == '0'|| record[row][column]) return 0;
  16.         record[row][column] = true;
  17.         flow(record,grid,row,column+1);
  18.         flow(record,grid,row+1,column);
  19.         flow(record,grid,row,column-1);
  20.         flow(record,grid,row-1,column);
  21.         return 1;
  22.     }
  23. }

官解（大同小异）

  1. class Solution {
  2.     void dfs(char[][] grid, int r, int c) {
  3.         int nr = grid.length;
  4.         int nc = grid[0].length;
  6.         if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
  7.             return;
  8.         }
  10.         grid[r][c] = '0';
  11.         dfs(grid, r - 1, c);
  12.         dfs(grid, r + 1, c);
  13.         dfs(grid, r, c - 1);
  14.         dfs(grid, r, c + 1);
  15.     }
  17.     public int numIslands(char[][] grid) {
  18.         if (grid == null || grid.length == 0) {
  19.             return 0;
  20.         }
  22.         int nr = grid.length;
  23.         int nc = grid[0].length;
  24.         int num_islands = 0;
  25.         for (int r = 0; r < nr; ++r) {
  26.             for (int c = 0; c < nc; ++c) {
  27.                 if (grid[r][c] == '1') {//减少递归
  28.                     ++num_islands;
  29.                     dfs(grid, r, c);
  30.                 }
  31.             }
  32.         }
  34.         return num_islands;
  35.     }
  36. }