LeetCodeDay49 —— 岛屿的个数★★☆

200. 岛屿的个数

描述

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

示例

示例 1
输入:
  11110
  11010
  11000
  00000
输出:
  1

示例 2
输入:
  11000
  11000
  00100
  00011
输出: 
  3

思路

1. 图深度优先遍历DFS的应用，依次遍历每一个点:
   1）若为1，则将其置为已访问，并递归遍历其周围4个点;
   2）若为0，则继续下一个点。
2. 可以不用额外利用一个 Visited 数组来标记是否"已访问"，访问过的节点直接置为 0 即可。(参考)

class Solution_200 {
 public:
  int numIslands(vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int rows = grid.size(), cols = grid[0].size();
    int ret = 0;
    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (grid[i][j] == '1') {
          ++ret;
          numIslandsDFS(grid, i, j);
        }
      }
    }
    return ret;
  }
  void numIslandsDFS(vector<vector<char>>& grid, int row, int col) {
    if (row < 0 || row >= grid.size()) return;
    if (col < 0 || col >= grid[0].size()) return;
    if (grid[row][col] == '0') return;
    grid[row][col] = '0';
    numIslandsDFS(grid, row - 1, col);
    numIslandsDFS(grid, row + 1, col);
    numIslandsDFS(grid, row, col - 1);
    numIslandsDFS(grid, row, col + 1);
  }
};