[LeetCode] 200. Number of Islands

• Problem: Number of Islands, 僅上下左右 (不包含對角線) 相鄰的 components (islands) 個數
• Limitation:
• Note:
• 注意 data type, namely, char 的 '0', hex 為 30, 不要拿來與 0 做比較
• 注意邊界條件, width, height 判斷依據為 >=, 若判斷條件有誤會跑不完
• Concept: 
• nIslands 計數後, 運用 DFS將相鄰的全設為 '0'
• Implementation:

• class Solution {
  public:
      void dfs(int i, int j, size_t width, size_t height, vector> &grid) {
          if (i < 0 || j < 0 || i >= width || j >= height || grid[i][j] == '0')
              return;
  
          grid[i][j] = '0';
  
          dfs(i    , j - 1, width, height, grid);
          dfs(i    , j + 1, width, height, grid);
          dfs(i - 1, j    , width, height, grid);
          dfs(i + 1, j    , width, height, grid);
      }
      
      int numIslands(vector>& grid) {
          int nIslands = 0;
          if(grid.empty()) return 0;
  
          const size_t width = grid.size();
          const size_t height = grid[0].size();
          
          for (size_t i = 0; i < width; i++) {
              assert (height == grid[i].size());
              for (size_t j = 0; j < height; j++) {
                  if (grid[i][j] - '0') {
                      nIslands++;
                      dfs(i, j, width, height, grid);
                  }
              }
          }
          
          return nIslands;
      }
  };