【C++算法】80.BFS解决FloodFill算法_岛屿数量

---

题目链接：

200. 岛屿数量

---

题目描述：

---

解法

BFS一层层剥开。

题目答案是这么来的。

注意：要防止之前已经被标记过的元素重复标记，防止拐回去。

可以采用两个方法：

1. 直接修改原数组（不推荐）

   • 初始元素的上下左右搜寻后，将初始元素置0

2. 建造一个vis[m][n]，和原始数组一样大，里面存放true和false，标记已经遍历过的数组。设置ret表示岛屿数量。一开始数组里面的初始元素1标为true，后面每标记一次就把对应的1标为true。只要后面遇到的1是false就继续。找完了再去找下一个连通块，同时ret++。

---

C++ 算法代码：

class Solution {// 定义四个方向的偏移量：下、上、右、左int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};// 标记数组，记录每个位置是否被访问过bool vis[301][301];// 网格的行数和列数int m, n;public:// 主函数：计算岛屿数量int numIslands(vector<vector<char>>& grid) {// 获取网格的行数和列数m = grid.size(), n = grid[0].size();int ret = 0;  // 记录岛屿数量// 遍历整个网格for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果当前位置是陆地且未被访问过if (grid[i][j] == '1' && !vis[i][j]) {ret++;  // 发现新岛屿bfs(grid, i, j);  // 使用BFS标记该岛屿所有陆地}}}return ret;  // 返回岛屿总数}// BFS辅助函数：标记与(i,j)相连的所有陆地void bfs(vector<vector<char>>& grid, int i, int j) {queue<pair<int, int>> q;  // 创建队列用于BFSq.push({i, j});  // 将起点加入队列vis[i][j] = true;  // 标记为已访问while (q.size()) {auto [a, b] = q.front();  // 取出队首元素q.pop();// 遍历四个方向for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];  // 计算新坐标// 检查新坐标是否有效if (x >= 0 && x < m && y >= 0 && y < n &&  // 边界检查grid[x][y] == '1' &&  // 是陆地!vis[x][y]) {  // 未访问过q.push({x, y});  // 加入队列vis[x][y] = true;  // 标记为已访问}}}}
};