当前位置：首页 > article >正文

[Lc15_bfs+floodfill] 图像渲染 | 岛屿数量 | 岛屿的最大面积 | 被围绕的区域

article 2025/3/19 6:21:30

1.图像渲染

题解

2.岛屿数量

题解

3.岛屿的最大面积

题解

4.被围绕的区域

题解

FloodFill 算法就是在一个矩阵中找性质相同的连通块。

关于这个后面会在《递归、搜索回溯专题》详细介绍。
并且用的是DFS解决问题，这里主要是用BFS解决FloodFill 算法。

1.图像渲染

链接：733. 图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

为了完成 上色工作：

从初始像素开始，将其颜色改为 color。
对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续重复此过程。
当没有其它原始颜色的相邻像素时停止操作。

最后返回经过上色渲染修改后的图像。

题解

这道题的意思是，给一个开始位置，把和它性质相同的连通块都找到，并且渲染成color。

注意可以上下左右四个方向去找。

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
//....
 //实现 上下左右四个方向 的移动
for(int i = 0; i < 4; ++i)
    int x = a + dx[i], y = b + dy[i];

解法：BFS

BFS(宽度优先遍历/宽度优先搜索/层序遍历)，借助队列实现，一层一层出。

起始位置先入队。
队列不空出队，把它上下左右和它颜色相同的放入队列。
然后循环下去，直到队列为空。

class Solution {
public:
    //在queue中对pair处理一下
    typedef pair<int,int> PII;
//bfs
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    vector<vector<int>> floodFill
    (vector<vector<int>>& image, int sr, int sc, int color) 
    {
        queue<PII> q;
        if(image[sr][sc]==color) return image;
    //record init color
        int prev=image[sr][sc];
        q.push({sr,sc});
        image[sr][sc] = color; // 入队后 着色

        int x_sz=image.size();
        int y_sz=image[0].size();

        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();

            for(int i=0;i<4;i++)
            {
                int x=a+dx[i],y=b+dy[i];
                if(x<x_sz && y<y_sz && x>=0 && y>=0
                    && image[x][y]==prev)
                    {
                        q.push({x,y});
                        image[x][y]=color;
                    }
            }
        }
        return image;
    }
};

2.岛屿数量

链接：200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

题解

求岛屿的数量，每座岛屿只能上下左右去找。

解法：BFS

从左往右扫描这个矩阵，当遇到陆地的时候就把和陆地相连的岛屿找到
如何找，就是BFS从这个地方宽搜一遍，就可以把连通的区域找到。
可以用一个变量ret 记录陆地数量就可以。

但是这里层序遍历有一个问题。从一个位置扩展到下一个位置

不能在从下一个位置在回到上一个位置不然就死循环了。

为了避免这种情况我们有两种方式。

1. 修改原始矩阵的值

2. 用一个同等矩阵大小的bool类型的二维数组，记录当前位置是否已经被搜索过

false表示没有，true表示搜索过。
并且当前位置bfs一次之后。和它相连的其他岛屿也被置为true
然后从左往右遍历的时候即使它是1，也不会进去了。

3.岛屿的最大面积

链接：695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

题解

这道题是求那一个连通块的面积是最大的。

解法：BFS

还是从左往右扫完，当碰到一块土地就去找和这个土地连通的所有土地，如何找？

还是用BFS遍历一次，同时要有一个变量count统计这个岛屿面积有多大。

注意找过的土地下一次不能在找了！
因此我们还是来一个bool类型的二维数组来标记那些土地是已经被搜索过了！

class Solution {
public:
    typedef pair<int,int> PII;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int row,col;
    vector<vector<bool>> vis;
    int ret=0;

    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        if(grid.empty()) return 0;
        row=grid.size();
        col=grid[0].size();
        vis.resize(row,vector<bool>(col,false));

        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]==1 && !vis[i][j])
                {
                    ret=max(ret,bfs(grid,i,j));
                }
            }
        }
        return ret;
    }

    int bfs(vector<vector<int>>& grid,int i,int j)
    {
        queue<PII> q;
        q.push({i,j});
        vis[i][j]=true;
        int count=1;

        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();

            for(int m=0;m<4;m++)
            {
                int x=a+dx[m],y=b+dy[m];
                if(x>=0 && x<row && y>=0 && y<col
                    && grid[x][y]==1 && !vis[x][y])
                    {
                        q.push({x,y});
                        vis[x][y]=true;
                        count++;
                    }
            }
        }
        return count;
    }
};