江苏有哪些网站建设的公司,动态速写网站,免费网站开发软件平台,美容院网站模板题1#xff1a;岛屿周长
给定一个 row x col 的二维网格地图 grid #xff0c;其中#xff1a;gridi 1 表示陆地#xff0c; gridi 0 表示水域。
网格中的格子 水平和垂直 方向相连#xff08;对角线方向不相连#xff09;。整个网格被水完全包围#xff0c;但其中恰…题1岛屿周长
给定一个 row x col 的二维网格地图 grid 其中gridi 1 表示陆地 gridi 0 表示水域。
网格中的格子 水平和垂直 方向相连对角线方向不相连。整个网格被水完全包围但其中恰好有一个岛屿或者说一个或多个表示陆地的格子相连组成的岛屿。
岛屿中没有“湖”“湖” 指水域在岛屿内部且不和岛屿周围的水相连。格子是边长为 1 的正方形。网格为长方形且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 思路 一块土地原则上会带来4个周长但岛上的土地存在接壤会减掉2个边长。
所以总周长4*土地个数-2*接壤边的条数
遍历矩阵遍历到土地就land如果它的右边或下边也是土地则border便遍历结束后代入公式即可。 Code:
int islandPerimeter(int** grid, int gridSize, int* gridColSize){int land0;//土地的块数int broader0;//土地接壤的块数for(int i0;igridSize;i){for(int j0;jgridColSize[i];j){if(grid[i][j]){land;//如果遍历到土地那么就landif(igridSize-1grid[i1][j])//如果土地的下方也是土地那么broader{broader;}if(jgridColSize[i]-1grid[i][j1])//如果土地的右方也是土地那么broader{broader;}}}}int result4*land-2*broader;//一块土地有四条边一个土地每接壤了一块土地就要少两条边//所以总边数4*土地块数-2*接壤土地块数return result;
} 题2岛屿数量
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
示例1 输入grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ] 输出1 示例2 输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 输出3 思路 本题我们可以采用递归算法来实现遍历矩阵找到陆地后开始递归查找当前位置的上下左右四个方向是否也为陆地。在这过程中要注意的是每访问一块陆地后要将其更新为0防止重复访问产生死循环。 Code
class Solution {
public:void dfs(vectorvectorchar grid,int i,int j){int ngrid.size();int mgrid[0].size();//访问过就更新为0grid[i][j]0;//继续判断上下左右四个方向是否是岛屿if(i-10 grid[i-1][j]1) dfs(grid,i-1,j);if(i1n grid[i1][j]1) dfs(grid,i1,j);if(j-10 grid[i][j-1]1) dfs(grid,i,j-1);if(j1m grid[i][j1]1) dfs(grid,i,j1);}int numIslands(vectorvectorchar grid) {int ngrid.size();int mgrid[0].size();int num0;//记录岛屿个数//遍历矩阵for(int i0;in;i){for(int j0;jm;j){//如果当前位置为陆地也就是为1则找它的上下左右相连的陆地if(grid[i][j]1){dfs(grid,i,j);//岛屿数量加1num;}}}return num;}
}; 题3统计子岛屿
你两个 m x n 的二进制矩阵 grid1 和 grid2 它们只包含 0 表示水域和 1 表示陆地。一个 岛屿 是由 四个方向 水平或者竖直上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿被 grid1 的一个岛屿 完全 包含也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。 示例 输入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 个子岛屿。 思路
1.首先要明确子岛屿的定义grid2 的一个岛屿必须被 grid1 的一个岛屿 完全 包含。
2.我们采用递归算法来实现本题
3.在写递归条件时我们需要考虑的是当遇到下标越界或是土地2的一个岛屿已经结束也就是grid2[i][j]!1时说明当前的这个子岛屿已经判断完毕return true
4.每访问一个位置就要将当前位置变成不是陆地这里我设置成2为了防止出现死循环设置过之后访问过的位置不会再次被访问
5.设置一个标记用来标记当前是否为子岛屿
6.每次都要判断上下左右四个方向是否是陆地且满足被包含在土地1的岛屿中 Code
class Solution {
public://坐标的偏移量上下左右四个方向int dx[4]{0,0,-1,1};int dy[4]{-1,1,0,0}; bool dfs(vectorvectorint grid1, vectorvectorint grid2,int i,int j){int ngrid1.size();int mgrid1[0].size();//如果不是陆地或越界返回trueif(in||i0||jm||j0||grid2[i][j]!1) return true;//访问过的位置置为2防止出现死循环grid2[i][j]2;//设置标记flag初始为truebool flagtrue;//如果土地1当前位置不是陆地则将flag置为flase在最后统一返回不能现在直接return不然会导致有些岛屿没有判断到if(grid1[i][j]0) flagfalse;//开始找上下左右四个方向for(int k0;k4;k){int xidx[k],yjdy[k];//这里flag必须两个条件相与如果上一轮flag为false那么说明土地1的岛屿没有完全包含土地2的岛屿即使此时两块土地的位置都为1也不符合题意flag仍然为falseflagdfs(grid1,grid2,x,y) flag;}return flag;}int countSubIslands(vectorvectorint grid1, vectorvectorint grid2) {int ngrid1.size();int mgrid1[0].size();int res0;//记录子岛屿的个数for(int i0;in;i){for(int j0;jm;j){//如果当前土地2的位置是陆地同时土地1的位置也是陆地才能进入递归//因为我们在递归中设置为只要不是陆地那么当前位置就是子岛屿所以进入递归的前提条件就是当前位置必须是陆地if(grid2[i][j]1 grid1[i][j]1){if(dfs(grid1,grid2,i,j))res;}}}return res;}
};
