# 1905. Count Sub Islands

• Time: $O(mn)$
• Space: $O(mn)$
  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: int countSubIslands(vector>& grid1, vector>& grid2) { int ans = 0; for (int i = 0; i < grid2.size(); ++i) for (int j = 0; j < grid2[0].size(); ++j) if (grid2[i][j] == 1) ans += dfs(grid1, grid2, i, j); return ans; } private: int dfs(const vector>& grid1, vector>& grid2, int i, int j) { if (i < 0 || i == grid1.size() || j < 0 || j == grid2[0].size()) return 1; if (grid2[i][j] != 1) return 1; grid2[i][j] = 2; // Mark 2 as visited return dfs(grid1, grid2, i + 1, j) & dfs(grid1, grid2, i - 1, j) & dfs(grid1, grid2, i, j + 1) & dfs(grid1, grid2, i, j - 1) & grid1[i][j]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int countSubIslands(int[][] grid1, int[][] grid2) { int ans = 0; for (int i = 0; i < grid2.length; ++i) for (int j = 0; j < grid2[0].length; ++j) if (grid2[i][j] == 1) ans += dfs(grid1, grid2, i, j); return ans; } private int dfs(int[][] grid1, int[][] grid2, int i, int j) { if (i < 0 || i == grid1.length || j < 0 || j == grid2[0].length) return 1; if (grid2[i][j] != 1) return 1; grid2[i][j] = 2; // Mark 2 as visited return dfs(grid1, grid2, i + 1, j) & dfs(grid1, grid2, i - 1, j) & dfs(grid1, grid2, i, j + 1) & dfs(grid1, grid2, i, j - 1) & grid1[i][j]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: m = len(grid2) n = len(grid2[0]) def dfs(i: int, j: int) -> int: if i < 0 or i == m or j < 0 or j == n: return 1 if grid2[i][j] != 1: return 1 grid2[i][j] = 2 # Mark 2 as visited return dfs(i + 1, j) & dfs(i - 1, j) & \ dfs(i, j + 1) & dfs(i, j - 1) & grid1[i][j] ans = 0 for i in range(m): for j in range(n): if grid2[i][j] == 1: ans += dfs(i, j) return ans