力扣第200题 岛屿数量

前言

记录一下刷题历程 力扣第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(vector<vector<char>>& grid) {int nums = 0; // 记录岛屿数量int rows = grid.size(); // 获取网格的行数if (!rows) return nums; // 如果行数为0，直接返回0int cols = grid[0].size(); // 获取网格的列数// 创建一个与grid同样大小的访问标记数组vector<vector<bool>> visit(rows, vector<bool>(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(vector<vector<char>>& grid, int row, int col, vector<vector<bool>>& visit) {queue<pair<int, int>> q; // 用队列来辅助BFS遍历q.push({row, col}); // 将当前起始点加入队列visit[row][col] = true; // 标记该点为已访问// 方向数组，表示上下左右四个方向vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// 当队列不为空时，持续执行BFSwhile (!q.empty()) {pair<int, 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; // 标记该点为已访问}}}}
};