广东的网站建设,鹤壁市城乡一体化示范区官网入口,珠海网站建设多少钱,1 高端品牌网站定制文章目录1. 题目2. 解题1. 题目
给你两个 m x n 的二进制矩阵 grid1 和 grid2 #xff0c;它们只包含 0 #xff08;表示水域#xff09;和 1 #xff08;表示陆地#xff09;。 一个 岛屿 是由 四个方向 #xff08;水平或者竖直#xff09;上相邻的 1 组成的区域。 任…
文章目录1. 题目2. 解题1. 题目
给你两个 m x n 的二进制矩阵 grid1 和 grid2 它们只包含 0 表示水域和 1 表示陆地。 一个 岛屿 是由 四个方向 水平或者竖直上相邻的 1 组成的区域。 任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿被 grid1 的一个岛屿 完全 包含也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。
示例 1
输入grid1 [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]],
grid2 [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出3
解释如上图所示左边为 grid1 右边为 grid2 。
grid2 中标红的 1 区域是子岛屿总共有 3 个子岛屿。示例 2
输入grid1 [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]],grid2 [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出2
解释如上图所示左边为 grid1 右边为 grid2 。
grid2 中标红的 1 区域是子岛屿总共有 2 个子岛屿。提示
m grid1.length grid2.length
n grid1[i].length grid2[i].length
1 m, n 500
grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-sub-islands 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
遍历地图2进行 BFS同时检查地图1要求不能包含水
class Solution {int m, n, ans 0;int color 2;vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1}};vectorvectorint grid1_copy;typedef pairint,int pii;
public:int countSubIslands(vectorvectorint grid1, vectorvectorint grid2) {m grid1.size(), n grid1[0].size();grid1_copy grid1;for(int i 0; i m; i){for(int j 0; j n; j){if(grid2[i][j] ! 1) continue;bfs(grid2, i, j);}}return ans;}void bfs(vectorvectorint g, int i, int j){queuepii q;q.push({i, j});color;g[i][j] color;bool water false;//遇到水while(!q.empty()){int x q.front().first;int y q.front().second;q.pop();if(grid1_copy[x][y] 0)water true;for(int k 0; k 4; k){int nx x dir[k][0];int ny y dir[k][1];if(nx0 nxm ny0 nyn g[nx][ny]1){q.push({nx, ny});g[nx][ny] color;}}}ans !water;}
};568 ms 218.7 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
