高端网页建设公司_江门网站推广设计_临沂seo网站管理_优化网站视频

题意

给定两个二维矩阵，grid1和grid2，都只含有0，1。 grid1和grid2中有很多不同的岛屿（由1构成），如果grid2中有一个岛屿满足这个岛屿所有的点在grid1矩阵中为都为’1’，那么这个岛屿被认为是一个sub island。求所有的sub islands

题目链接

https://leetcode.com/problems/count-sub-islands/description/

思考

这题跟number of islands很像，但是唯一不同的是计数方式，除了把岛2中的已经遍历过的岛mark成visited之外我还需要有一个返回值来判断这个岛屿是不是sub islands，判断的方法是如果岛2中的岛屿中的点有一个在岛1的矩阵中为0那么我就不认为这是一个sub island

解答

遍历岛2，当遇到‘1’的时候，用dfs 遍历岛屿并且把这些mark成visit，同时我需要返回这个岛屿是否是满足所有在岛1对应的点上都为1的判断

class Solution {
public:int m;int n;int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {m = grid2.size();n = grid2[0].size();int res = 0;vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid2[i][j] == 1 && !vis[i][j]) {if(dfs(grid1, grid2, i, j, vis)) {res++;}}}}return res;}bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int x, int y, vector<vector<bool>>& vis) {vis[x][y] = true;int dk[] = {-1, 0, 1, 0, -1};bool isValid = false;if(grid1[x][y] == 1) {isValid = true;}for(int i = 0; i < 4; i++) {int nx = x + dk[i];int ny = y + dk[i+1];if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid2[nx][ny] == 1 && !vis[nx][ny]) {isValid = isValid & dfs(grid1, grid2, nx, ny, vis);}}return isValid;}
};

时间复杂度：$O(mn)$ m,n是grid的长宽
空间复杂度：$O(mn)$ m,n是grid的长宽