leetcode

0

1 class Solution {

2 public:

3 int countSubIslands(const vector<vector<int>> &grid1, vector<vector<int>> &grid2) {

4 static constexpr const int offset_x[] = {0, 0, 1, -1};

5 static constexpr const int offset_y[] = {1, -1, 0, 0};

6 const int n = grid1.size(), m = grid1[0].size();

7 const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };

8

9 int res = 0;

10 for (int i = 0; i < n; i++) {

11 for (int j = 0; j < m; j++) {

12 if (!grid2[i][j] || !grid1[i][j]) continue;

13 grid2[i][j] = 0;

14 queue<pair<int, int>> q({{i, j}});

15 bool sub = true;

16 while (!q.empty()) {

17 const auto [i, j] = q.front();

18 q.pop();

19 for (int k = 0; k < 4; k++) {

20 const int x = i + offset_x[k];

21 const int y = j + offset_y[k];

22 if (!valid(x, y) || !grid2[x][y]) continue;

23 if (!grid1[x][y]) sub = false;

24 grid2[x][y] = 0;

25 q.push({x, y});

26 }

27 }

28 res += sub;

29 }

30 }

31 return res;

32 }

33 };