Flood Fill 算法模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方向数组
dx[4] = {-1, 0, 1, 0}
dy[4] = {0, 1, 0, -1}

for i=0 to n
  for j=0 to m
    if (i, j) 未遍历
      则遍历 (i, j)

dfs(x, y)
  标记(x, y)为已遍历
  for (遍历四个方向)
    计算将要遍历的下一个格子的坐标 (a, b)
    if ((a, b)不越界且可以遍历)
      dfs(a, b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<vector<char>> g;
  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  int numIslands(vector<vector<char>>& grid) {
    g = grid;
    int cnt = 0;
    for (int i = 0; i < g.size(); i++) {
      for (int j = 0; j < g[i].size(); j++) {
        if (g[i][j] == '1') {
          dfs(i, j);
          cnt++;
        }
      }
    }
    return cnt;
  }
  void dfs(int x, int y) {
    g[x][y] = '0';
    for (int i = 0; i < 4; i++) {
      int a = x + dx[i], b = y + dy[i];
      if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() &&
          g[a][b] == '1') {
        dfs(a, b);
      }
    }
  }
}

每个格子遍历一次，算法时间复杂度为 O(n*m)