200. Number of Islands

This problem can be solved by DFS. The idea is once we encounter a '1', we must have an island. Then we make it "water" (i.e. flip '1' to '0') and scan the surrounding areas. As a result, the island becomes sea in the end and we scan the matrix again until we find a new island again.

1:  class Solution {  
2:  private:  
3:    vector<pair<int, int>> dir;  
4:    int row;  
5:    int col;  
6:  public:  
7:    int numIslands(vector<vector<char>>& grid) {  
8:      row = grid.size();  
9:      if (row == 0) return 0;  
10:      col = grid[0].size();  
11:      int count = 0;  
12:      dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
13:      for (int i = 0; i < row; i++) {  
14:        for (int j = 0; j < col; j++) {  
15:          if (grid[i][j] == '1') {  
16:            count++;  
17:            dfs(grid, i, j);  
18:          }  
19:        }  
20:      }  
21:      return count;  
22:    }  
23:    void dfs(vector<vector<char>> &grid, int i, int j) {  
24:      grid[i][j] = '0';  
25:      for (int k = 0; k < dir.size(); k++) {  
26:        int ii = i + dir[k].first;  
27:        int jj = j + dir[k].second;  
28:        if (ii < 0 || ii == row || jj < 0 || jj == col || grid[ii][jj] == '0') continue;  
29:        dfs(grid, ii, jj);  
30:      }  
31:    }  
32:  };