网站开发产生的材料,合肥建站网站模板,网页托管平台排名,谷歌排名推广前言
记录一下刷题历程 力扣第200题 岛屿数量 岛屿数量
原题目#xff1a; 给你一个由 ‘1’#xff08;陆地#xff09;和 ‘0’#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平…前言
记录一下刷题历程 力扣第200题 岛屿数量 岛屿数量
原题目 给你一个由 ‘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
分析
网格由’1’陆地和’0’水域组成岛屿被定义为一组相连的陆地。相连的陆地可以是水平或垂直相邻但不能是对角线相邻。我们使用广度优先搜索从某个节点出发始终优先访问距离最近的顶点并一层层向外扩张来搜索每一个岛屿我们可以使用一个队列来辅助BFS搜索
代码如下
class Solution {
public:// 计算岛屿数量的主函数int numIslands(vectorvectorchar grid) {int nums 0; // 记录岛屿数量int rows grid.size(); // 获取网格的行数if (!rows) return nums; // 如果行数为0直接返回0int cols grid[0].size(); // 获取网格的列数// 创建一个与grid同样大小的访问标记数组vectorvectorbool visit(rows, vectorbool(cols, false));// 遍历网格中的每一个元素for (int row 0; row rows; row) {for (int col 0; col cols; col) {// 如果当前元素为1表示陆地且没有被访问过if (grid[row][col] 1 !visit[row][col]) {bfs(grid, row, col, visit); // 执行BFS遍历nums; // 每发现一个岛屿岛屿数量1}}}return nums; // 返回最终的岛屿数量}// BFS函数用来遍历一个岛屿的所有部分void bfs(vectorvectorchar grid, int row, int col, vectorvectorbool visit) {queuepairint, int q; // 用队列来辅助BFS遍历q.push({row, col}); // 将当前起始点加入队列visit[row][col] true; // 标记该点为已访问// 方向数组表示上下左右四个方向vectorvectorint dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// 当队列不为空时持续执行BFSwhile (!q.empty()) {pairint, int temp q.front(); // 获取队列头部的坐标q.pop(); // 弹出队列头部// 遍历当前节点的上下左右四个方向for (int i 0; i dirs.size(); i) {int temp_row temp.first dirs[i][0]; // 计算新的行坐标int temp_col temp.second dirs[i][1]; // 计算新的列坐标// 检查新坐标是否在网格范围内是否为1且未访问过if (temp_row 0 temp_row grid.size() temp_col 0 temp_col grid[0].size() grid[temp_row][temp_col] 1 !visit[temp_row][temp_col]) {q.push({temp_row, temp_col}); // 将新坐标加入队列visit[temp_row][temp_col] true; // 标记该点为已访问}}}}
};
