曲靖网站建设0doit,网站建设中素材,重庆网站,php网站设置如何使用1. 题目链接#xff1a;200. 岛屿数量
2. 题目描述#xff1a; 给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上…1. 题目链接200. 岛屿数量
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提示 m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 0 或 1 3. 算法思路
初始化一个与输入网格大小相同的二维布尔数组 vis用于记录每个位置是否已经被访问过。初始时所有位置都未被访问过所以 vis 中的所有元素都为 false。获取输入网格的行数 m 和列数 n。定义一个整数变量 ret用于记录岛屿的数量。初始值为 0。使用两层嵌套循环遍历整个网格。对于每个位置 (i, j)执行以下操作 如果该位置未被访问过且其值为 ‘1’表示陆地则将 ret 的值加一并调用 dfs 函数进行深度优先搜索。 在 dfs 函数中将当前位置标记为已访问即将 vis[i][j] 设置为 true。使用四个方向的偏移量 dx 和 dy分别表示上、下、左、右四个方向。对于每个方向计算新的坐标 (x, y)并检查其是否在网格范围内且未被访问过且值为 ‘1’。如果满足条件则递归调用 dfs 函数继续搜索相邻的陆地。当所有位置都被访问过后返回岛屿的数量 ret。 4. C算法代码
class Solution {vectorvectorbool vis; // 用于记录访问过的岛屿位置int m, n; // 网格的行数和列数
public:// 计算岛屿的数量int numIslands(vectorvectorchar grid) {m grid.size(), n grid[0].size();vis vectorvectorbool(m, vectorbool(n));int ret 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (!vis[i][j] grid[i][j] 1) { // 如果当前位置未被访问过且为陆地ret; // 岛屿数量加一dfs(grid, i, j); // 进行深度优先搜索}}}return ret;}int dx[4] {0, 0, 1, -1}; // x轴方向的偏移量int dy[4] {1, -1, 0, 0}; // y轴方向的偏移量// 深度优先搜索函数void dfs(vectorvectorchar grid, int i, int j) {vis[i][j] true; // 标记当前位置已访问for (int k 0; k 4; k) {int x i dx[k], y j dy[k]; // 计算相邻位置的坐标if (x 0 x m y 0 y n !vis[x][y] grid[x][y] 1) { // 如果相邻位置在网格内且未被访问过且为陆地dfs(grid, x, y); // 继续进行深度优先搜索}}}
};
