手机网站建设代理商,南昌专业网站建设机构,户县做网站,网站首页地址是什么文章目录1. 题目2. 解题2.1 DFS2.2 BFS1. 题目
有一个二维矩阵 grid #xff0c;每个位置要么是陆地#xff08;记号为 0 #xff09;要么是水域#xff08;记号为 1 #xff09;。
我们从一块陆地出发#xff0c;每次可以往上下左右 4 个方向相邻区域走#xff0c;能…
文章目录1. 题目2. 解题2.1 DFS2.2 BFS1. 题目
有一个二维矩阵 grid 每个位置要么是陆地记号为 0 要么是水域记号为 1 。
我们从一块陆地出发每次可以往上下左右 4 个方向相邻区域走能走到的所有陆地区域我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围即陆地边缘上下左右所有相邻区域都是水域那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
示例 1输入grid [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出2
解释
灰色区域的岛屿是封闭岛屿因为这座岛屿完全被水域包围即被 1 区域包围。示例 2输入grid [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出1示例 3
输入grid [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]
输出2提示
1 grid.length, grid[0].length 100
0 grid[i][j] 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-closed-islands 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
套路解题题目可以总结为搜索的过程中不能出界出界了就不算封闭岛屿
2.1 DFS
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m,n;
public:int closedIsland(vectorvectorint grid) {//可以总结为找的过程中不能出界出界的岛屿不算int i, j, island 0;m grid.size(), n grid[0].size();bool out;for(i 0; i m; i){for(j 0; j n; j){if(grid[i][j] 0)//陆地{out false;//出界了吗grid[i][j] 1;//访问过了无需回溯直接改dfs(grid,i,j,out);if(!out)//没有出界island;}}}return island;}void dfs(vectorvectorint grid, int i, int j, bool out){int x, y, k;for(k 0; k 4; k){x idir[k][0];y jdir[k][1];if(x0 xm y0 yn){ //在范围内是陆地if(grid[x][y] 0){grid[x][y] 1;//访问过dfs(grid,x,y,out);}}else//不在范围内out true;}}
};2.2 BFS
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m,n;
public:int closedIsland(vectorvectorint grid) {//可以总结为找的过程中不能出界出界的岛屿不算int i, j, island 0, x, y, k;m grid.size(), n grid[0].size();queuepairint,int q;pairint,int tp;bool out;for(i 0; i m; i){for(j 0; j n; j){if(grid[i][j] 0)//陆地{out false;grid[i][j] 1;//访问过了无需回溯直接改q.push({i,j});while(!q.empty()){tp q.front();q.pop();for(k 0; k 4; k){x tp.first dir[k][0];y tp.second dir[k][1];if(x0 xm y0 yn){ //在范围内是陆地if(grid[x][y] 0){grid[x][y] 1;//访问过q.push({x,y});}}else//不在范围内out true;}}if(!out)island;}}}return island;}
};
