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

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

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

示例 1：

  1. Input: grid = [
  2.   ["1","1","1","1","0"],
  3.   ["1","1","0","1","0"],
  4.   ["1","1","0","0","0"],
  5.   ["0","0","0","0","0"]
  6. ]
  7. Output: 1

示例 2：

  1. Input: grid = [
  2.   ["1","1","0","0","0"],
  3.   ["1","1","0","0","0"],
  4.   ["0","0","1","0","0"],
  5.   ["0","0","0","1","1"]
  6. ]
  7. Output: 3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 ≤ m, n ≤ 300
  • grid[i][j] is '0' or '1'.

思路

想象我们拿个颜料桶，从(0, 0) 的位置开始遍历整个图，当遇到小岛'1'时，我们就给把颜料涂在地上；当遇到水'0'时，我们就不涂颜色。

我们需要维护一个int color[][]数组，里面的值表示不同的颜色（也表示不同的小岛）。我们遍历完整个图，再数一数我们用了几种颜色就求出小岛的数量了。

DFS到什么时候停止呢？当我们走到一个涂过颜色的方格，我们就停止继续深度优先搜索。

DFS如何遍历周围的节点？我们按照题目要求判断垂直方向，水平方向没有越界，然后上下左右四个方向分别来一次DFS就行了。

代码

  1. class Solution {
  2. public:
  3.     int nums_of_island = 0;
  5.     int numIslands(vector<vector<char>>& grid) {
  6.         if( grid.size() == 0 )      return 0;  // null set
  7.         if( grid[0].size() == 0 )   return 0;  // null col
  9.         int color[ grid.size() ][ 300 ];
  10.         memset(color, 0x0, sizeof(color));
  12.         // Walk every node in grid
  13.         for(int i = 0; i < grid.size(); i++) {
  14.             for(int j = 0; j < grid[0].size(); j++) {
  15.                 if( color[i][j] == 0 && grid[i][j] == '1' ) {
  16.                     (this->nums_of_island)++;
  17.                     dfs(grid, color, i, j);
  18.                 }
  19.             }
  20.         }
  22.         return this->nums_of_island;
  23.     }
  25.     void dfs(vector<vector<char>>& grid, int color[][300], int row, int col) {
  26.         // 1. Exit condition
  27.         if( color[row][col] != 0 )   return;
  29.         // 2. Walk 4 directions of each node
  30.         if( grid[row][col] == '1' ) {
  31.             color[row][col] = this->nums_of_island;  // color the ground
  32.             if( row-1 >= 0 )            dfs( grid, color, row-1, col );  // Up
  33.             if( row+1 < grid.size() )   dfs( grid, color, row+1, col );  // Down
  34.             if( col-1 >= 0 )            dfs( grid, color, row, col-1 );  // left
  35.             if(col+1 < grid[0].size())  dfs( grid, color, row, col+1 );  // right
  36.         }
  37.     }
  38. };