# LeetCode Medium 200. Number of Islands

tags: leetcode

問題

• Explore
• Problems

アイデア

島を1が縦横に繋がったものと考えて，0を海と考えます．このときに，島の数を返せという問題です．

蟻本の冒頭に類題がありました．DFS，BFSを使って解くことが可能です．

解法1(DFS･再帰)

• 現在の位置が島ならば
  • そこから再帰的に探索します．
• 島でないならば
  • 探索終了

これを全ての点で行うだけです．

毎回，訪れた島は海に変えておきます．これによって同じ島を複数回カウントしなくて済みます．

計算量

縦横の長さをそれぞれH, Wとします．

• 時間計算量
  • 最悪全てのgridを探索するので$O(HW)$
• 空間計算量
  • 同様に再帰も最悪$O(HW)$するので空間計算量は$O(HW)$

C++

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) {
      return 0;
    }
    int cnt = 0;

    int height = grid.size(), width = grid[0].size();
    for (int h = 0; h < height; ++h) {
      for (int w = 0; w < width; ++w) {
        if (grid[h][w] == '1') {
          bfs(h, w, height, width, grid);
          ++cnt;
        }
      }
    }
    return cnt;
  }

private:
  void bfs(int _y, int _x, int _height, int _width, vector<vector<char>>& grid) {
    grid[_y][_x] = '0';
    for (int dy = -1; dy <= 1; ++dy) {
      for (int dx = -1; dx <= 1; ++dx) {
        if (dy + dx == 0 || abs(dy + dx) == 2)
          continue;
        int ny = _y + dy, nx = _x + dx;
        if (0 <= ny && ny < _height && 0 <= nx && nx < _width && grid[ny][nx] == '1')
          bfs(ny, nx, _height, _width, grid);
      }
    }
    return;
  }
};