leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1905.cpp (1273B)

      1 
      2 class Solution {
      3   public:
      4     int countSubIslands(const vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
      5         static constexpr const int offset_x[] = {0, 0, 1, -1};
      6         static constexpr const int offset_y[] = {1, -1, 0, 0};
      7         const int n = grid1.size(), m = grid1[0].size();
      8         const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
      9 
     10         int res = 0;
     11         for (int i = 0; i < n; i++) {
     12             for (int j = 0; j < m; j++) {
     13                 if (!grid2[i][j] || !grid1[i][j]) continue;
     14                 grid2[i][j] = 0;
     15                 queue<pair<int, int>> q({{i, j}});
     16                 bool sub = true;
     17                 while (!q.empty()) {
     18                     const auto [i, j] = q.front();
     19                     q.pop();
     20                     for (int k = 0; k < 4; k++) {
     21                         const int x = i + offset_x[k];
     22                         const int y = j + offset_y[k];
     23                         if (!valid(x, y) || !grid2[x][y]) continue;
     24                         if (!grid1[x][y]) sub = false;
     25                         grid2[x][y] = 0;
     26                         q.push({x, y});
     27                     }
     28                 }
     29                 res += sub;
     30             }
     31         }
     32         return res;
     33     }
     34 };