两道题差不多，暴力BFS跑就可以了，在插入队列的时候直接改变对应坐标上的标记速度会比队列遍历到再改变更快点。

200. 岛屿数量

 1 class Solution {
 2 public:
 3     int dx[4] = {-1, 1, 0, 0};
 4     int dy[4] = {0, 0, -1, 1};
 5     int numIslands(vector<vector<char>>& grid) {
 6         int ans = 0;
 7         pair<int, int> p;
 8         queue<pair<int, int>> q;
 9         for (int i = 0; i < grid.size(); i++) {
10             for (int j = 0; j < grid[i].size(); j++) {
11                 if (grid[i][j] != '0') {
12                     ans++;
13                     q.push(make_pair(i, j));
14                     while (!q.empty()) {
15                         p = q.front();
16                         q.pop();
17                         for (int k = 0; k < 4; k++) {
18                             int nx = p.first + dx[k];
19                             int ny = p.second + dy[k];
20                             if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[nx].size() && grid[nx][ny] == '1') 
21                             {q.push(make_pair(nx, ny));
22                             grid[nx][ny] = '0';}
23                         }
24                     }
25                 }
26             }
27         }
28         return ans;
29     }
30 };

View Code

面试题 16.19. 水域大小

 1 class Solution {
 2 public:
 3     vector<int> pondSizes(vector<vector<int>>& land) {
 4         vector<int> ans;
 5         int n = land.size();
 6         int m = land[0].size();
 7         queue<pair<int, int>> q;
 8         for (int i = 0; i < n; i++) {
 9             for (int j = 0; j < m; j++) {
10                 if (land[i][j] == 0) {
11                     int cnt = 1;
12                     q.push({i, j});
13                     land[i][j] = 1;
14                     while (!q.empty()) {
15                         auto p = q.front();
16                         q.pop();
17                         for (int l = -1; l <= 1; l++) {
18                             for (int r = -1; r <= 1; r++) {
19                                 int nx = l + p.first;
20                                 int ny = r + p.second;
21                                 if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
22                                 land[nx][ny] == 0) {
23                                     cnt++;
24                                     land[nx][ny] = 1;
25                                     q.push({nx, ny});
26                                 }
27                             }
28                         }
29                     }
30                     ans.push_back(cnt);
31                 }
32             }
33         }
34         sort(ans.begin(), ans.end());
35         return ans;
36     }
37 };

View Code