leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1905.cpp (1273B)

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 };