FloodFill算法——岛屿数量

本文主要是介绍FloodFill算法——岛屿数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目解析
算法解析
代码解析

题目解析

岛屿数量
在这里插入图片描述
题目依旧是熟悉的配方，熟悉的味道，还是那个0还是那个1还是那个二维矩阵，这时候BFS和DFS闻着味就来了，我们来看一下这个题目，这个题目也很容易理解如下图有一个二维矩阵

在这里面0是海洋1是陆地但是如果两个1是相邻的那么就是一个陆地，最终求出陆地的数量我们来看一下这个样列不难看出陆地的数量是3个那么这里你看懂的话恭喜你这个题目的意思你就懂了

算法解析

那么这个问题应该采取何种思路和方法呢？还记得BFS的步骤嘛？走前走后走左右，顾前顾后顾左右，满足要求改为true，不满要求不进队，那么这个题目我们按照我编的这个句子来看一下，首先用两层for循环取遍历这里面所有的节点，当节点为1的时候我们就来看看，它的前后左右如果，然后将他的前后左右满足条件的进入队列，并将加入队列的元素逐个遍历去获取他们的前后左右，并且这还不是最主要的是需要对我们遍历到的节点进行标记。从而保证符合要求的节点只会被我们遍历一次。

代码解析

class Solution {
public:int dx[4] = { 0,0,-1,1 };int dy[4] = { 1,-1,0,0 };bool vir[1010][1010];int numIslands(vector<vector<char>>& grid) {int ans = 0;int m = grid.size();int n = grid[0].size();for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {if (grid[i][j] == '1' && vir[i][j] == false) {ans++;vir[i][j] = true;bfs(i, j, grid,m,n);}}}return ans;}void bfs(int i, int j, vector<vector<char>>&grid,int m,int n) {queue<pair<int, int>>q;q.push({ i,j });while (q.size()) {auto [a, b] = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && vir[x][y] == false && grid[x][y] == '1') {q.push({ x,y });vir[x][y] = true;}}}}
};