[LeetCode] 200. Number of Island

原题

0代表水，1代表陆地，边界土地的上下左右不相连其他土地，则称为一块陆地。
计算有几块陆地。
思路：
DFS，从起点开始，每碰到一个‘1’，就作为DFS起点，将其相近的‘1’全部变为‘0’。直到无‘1’。

一开始dfs没有传参数组长度，而是每一次都调用size()，速度很慢
Runtime: 12 ms, faster than 47.97%
修改以后
Runtime: 8 ms, faster than 98.94%

class Solution
{
public:
  int numIslands(vector<vector<char>> &grid)
  {
    int res = 0;
    if (grid.empty())
      return res;
    int rowSize = grid.size();
    int colSize = grid[0].size();
    for (int i = 0; i < rowSize; i++)
    {
      for (int j = 0; j < colSize; j++)
      {
        if (grid[i][j] == '1')
        {
          dfs(grid, i, j, rowSize, colSize);
          res++;
        }
      }
    }
    return res;
  }
  void dfs(vector<vector<char>> &grid, int row, int col, int rs, int cs)
  {
    if (grid[row][col] == '1')
    {
      grid[row][col] = '0';
      if (row > 0 && grid[row - 1][col] == '1')
        dfs(grid, row - 1, col, rs, cs);
      if (row < grid.size() - 1 && grid[row + 1][col] == '1')
        dfs(grid, row + 1, col, rs, cs);
      if (col > 0 && grid[row][col - 1] == '1')
        dfs(grid, row, col - 1, rs, cs);
      if (col < grid[0].size() - 1 && grid[row][col + 1] == '1')
        dfs(grid, row, col + 1, rs, cs);
    }
  }
};