devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

BFS：Floodfill算法_bfs flood-fill

作者：小惠珠哦 | 2024-07-09 21:41:06

赞

踩

bfs flood-fill

Floodfill，翻译为洪水灌溉，而floodfill算法本质上是为了解决在矩阵中性质相同的联通块问题。

 一、图像渲染

. - 力扣（LeetCode）

        与dfs一样，从指定的起点开始向四个方向扩展，区别就是用之前通过参数将下标关系传递给dfs，而现在是将下标关系的键值对传给queue。

  1. class Solution {
  2. public:
  3.  //定义4个方向
  4.     int dx[4]={0,0,1,-1};
  5.     int dy[4]={1,-1,0,0};
  6.     typedef pair<int,int> PII;
  7.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
  8.     {
  9.       //采用BFS算法解决floodfill算法，  解决相同性质的矩阵联通块问题
  10.        int prev=image[sr][sc];
  11.        if(prev==color) return image;
  12.        int m=image.size(),n=image[0].size();
  13.        queue<PII> q;//队列
  14.        q.emplace(sr,sc);
  15.        while(!q.empty())
  16.        {
  17.          //先修改当前位置
  18.          auto [a,b]=q.front();//c++14的玩法
  19.          q.pop();
  20.          image[a][b]=color;//修改成color
  21.          for(int k=0;k<4;++k) 
  22.          {
  23.             int x=dx[k]+a,y=dy[k]+b;
  24.             if(x>=0&&x<m&&y>=0&&y<n&& image[x][y]==prev)
  25.                  q.emplace(x,y);
  26.          }
  27.        }
  28.        return image;
  29.     }
  30. };

 二、岛屿数量

. - 力扣（LeetCode）

 

  1.  因为要计算岛屿的数量，所以我们每进行一次bfs就要统计一下该岛屿，因为我们可以将bfs单独封装成一个函数。

  2.在扩展的时候，我们需要标记我们扩展过的网格，这里有两种方案：

（1）修改值，但是修改值会改变原数据，必须要想办法修改回来。

（2）标记数组（常用），相同大小的标记数组，将探索过的网格标记为true

  1. class Solution {
  2. public:
  3.     int dx[4]={1,-1,0,0};
  4.     int dy[4]={0,0,1,-1};
  5.     typedef pair<int,int> PII;
  6.     int m,n;//因为要单独封装一个BFS
  7.     bool check[301][301];//标记数组 看看哪些点是选过的 
  8.     int numIslands(vector<vector<char>>& grid) {
  9.         //ret统计一共有多少个联通块
  10.         int ret=0;
  11.         //直接修改原数组的话 可能会有问题
  12.         m=grid.size();
  13.         n=grid[0].size();
  14.         for(int i=0;i<m;++i)
  15.           for(int j=0;j<n;++j)
  16.              if(grid[i][j]=='1'&&check[i][j]==false) 
  17.              {
  18.                 ++ret;
  19.                 bfs(grid,i,j);
  20.              }
  21.        return ret;
  22.     }
  23.     void bfs(vector<vector<char>>& grid,int i,int j)
  24.     {
  25.         queue<PII> q;//队列统计下标实现BFS
  26.         q.emplace(i,j);
  27.         check[i][j]=true;
  28.         while(!q.empty())
  29.         {
  30.             auto [a,b]=q.front();
  31.             q.pop();
  32.             for(int k=0;k<4;++k)
  33.             {
  34.                 int x=dx[k]+a,y=dy[k]+b;
  35.                 if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&check[x][y]==false)
  36.                 {
  37.                    q.emplace(x,y);
  38.                    check[x][y]=true;
  39.                 }
  40.             }
  41.         }
  42.      }
  43. };

三、岛屿的最大面积

. - 力扣（LeetCode）

         我们需要统计每个岛屿的大小，所以我们可以将bfs单独封装成一个函数，然后利用他的返回值返回岛屿的大小，在主函数中去更新找到最大值。 

  1. class Solution {
  2. public:
  3.     int dx[4]={1,-1,0,0};
  4.     int dy[4]={0,0,1,-1};
  5.     typedef pair<int,int> PII;
  6.     int m,n;//因为要单独封装一个BFS
  7.     bool check[50][50];//标记数组 看看哪些点是选过的
  8.     int maxAreaOfIsland(vector<vector<int>>& grid) 
  9.     {
  10.         int ret=0;//统计最大岛屿数量
  11.         m=grid.size(),n=grid[0].size();
  12.         for(int i=0;i<m;++i)
  13.           for(int j=0;j<n;++j)
  14.              if(grid[i][j]==1&&check[i][j]==false)
  15.                  ret=max(bfs(grid,i,j),ret);
  16.             return ret;
  17.     }
  18.     int bfs(vector<vector<int>>& grid,int i,int j)
  19.     {
  20.         queue<PII> q;
  21.         q.emplace(i,j);
  22.         check[i][j]=true;
  23.         int count=1;
  24.         while(!q.empty())
  25.         {
  26.             auto [a,b]=q.front();
  27.             q.pop();
  28.             for(int k=0;k<4;++k)
  29.             {
  30.                 int x=dx[k]+a,y=dy[k]+b;
  31.                 if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&check[x][y]==false)
  32.                   {
  33.                     check[x][y]=true;
  34.                     q.emplace(x,y);
  35.                     ++count;
  36.                   }
  37.             }
  38.         }
  39.         return count;
  40.     }
  41. };

 四、被围绕的区域

. - 力扣（LeetCode）

        如果直接做的话，我们会发现如果我们处理一个区域的时候一旦触碰到边界，那么就全部需要回头。或者说得先遍历一遍，确认这个联通块没有触碰边界，然后再遍历一次去标记，这样显然效率是很低的。因此我们的解决方案就是正难则反。 

（1）先从边界走一波bfs，将O全部修改成 .

（2）然后遍历矩阵（遍历矩阵的时候可以顺便还原，所以这个地方我们就不需要设置标记数组），将剩下的O修改成X，然后将.还原成O。

  1. class Solution {
  2. public:
  3.     const int dx[4]={1,-1,0,0};
  4.     const int dy[4]={0,0,1,-1};
  5.     typedef pair<int,int> PII;
  6.     int m,n;//因为要单独封装一个BFS
  7.     void solve(vector<vector<char>>& board) {
  8.       m=board.size(),n=board[0].size();
  9.       //先处理第一行和最后一行
  10.       for(int j=0;j<n;++j)
  11.       {
  12.         if(board[0][j]=='O') bfs(board,0,j);
  13.         if(board[m-1][j]=='O') bfs(board,m-1,j);
  14.       }
  15.       //处理第一列和最后一列
  16.       for(int i=0;i<m;++i)
  17.       {
  18.         if(board[i][0]=='O') bfs(board,i,0);
  19.         if(board[i][n-1]=='O') bfs(board,i,n-1);
  20.       }
  21.       //进行复原
  22.       for(int i=0;i<m;++i)
  23.        for(int j=0;j<n;++j)
  24.          if(board[i][j]=='O') board[i][j]='X';
  25.           else if(board[i][j]=='.') board[i][j]='O';
  26.     }
  27.     void bfs(vector<vector<char>>& board,int i,int j)
  28.     {
  29.         queue<PII> q;
  30.         q.emplace(i,j);
  31.         board[i][j]='.';
  32.         while(!q.empty())
  33.         {
  34.             auto [a,b]=q.front();
  35.             q.pop();
  36.             for(int k=0;k<4;++k) 
  37.             {
  38.                 int x=dx[k]+a,y=dy[k]+b;
  39.                 if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O')
  40.                   {
  41.                     q.emplace(x,y);
  42.                     board[x][y]='.';
  43.                   }
  44.             }
  45.         }
  46.     }
  47. };

五、太平洋大西洋水流问题

. - 力扣（LeetCode）

        如果我们直接做的话，显然需要需要遍历矩阵，然后每遍历一个点就要判断该点是否可以同时流向太平洋和大西洋，显然这样是十分麻烦的。因此我们的思路就是正难则反。

 （1）从矩阵的边界开始逆推（从低往高处流）

（2）用两个标记数组进行标记，一个标记表示可以流向太平洋，另一个标记可以流向大西洋，最后我们将两个标记数组都标记过的坐标进行统计并返回即可。

  1. class Solution {
  2. public:
  3.     const int dx[4]={0,0,-1,1};
  4.     const int dy[4]={1,-1,0,0};
  5.     int m,n;
  6.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) 
  7.     {
  8.        //正难则反  用两个标记数组，用边界去往中间走，将能走的位置给标记了
  9.        //最后两个标记数组都被标记的地方就是我们最终的结果
  10.        m=h.size(),n=h[0].size();
  11.        //定义两个标记数组
  12.        vector<vector<bool>> atl(m,vector<bool>(n));
  13.        auto pac=atl;
  14.        //先探索行
  15.        for(int i=0;i<m;++i) 
  16.        {
  17.         bfs(h,i,0,pac);
  18.         bfs(h,i,n-1,atl);
  19.        }
  20.        //探索列
  21.         for(int j=0;j<n;++j) 
  22.        {
  23.         bfs(h,0,j,pac);
  24.         bfs(h,m-1,j,atl);
  25.        }
  26.        //遍历一下 如果标记数组都存在，就返回结果
  27.        vector<vector<int>> ret;
  28.        for(int i=0;i<m;++i)
  29.          for(int j=0;j<n;++j)
  30.            if(pac[i][j]&&atl[i][j])
  31.              ret.push_back({i,j});
  32.        return ret;
  33.     }
  34.  
  35.     void bfs(vector<vector<int>>& h,int i,int j,vector<vector<bool>>&vis)
  36.     {
  37.         queue<pair<int,int>> q;
  38.         q.emplace(i,j);
  39.         vis[i][j]=true;
  40.         while(!q.empty())
  41.         {
  42.             auto [a,b]=q.front();
  43.             q.pop();
  44.             for(int k=0;k<4;++k)
  45.              {
  46.                 int x=dx[k]+a,y=dy[k]+b;
  47.                 if(x>=0&&x<m&&y>=0&&y<n&&h[x][y]>=h[a][b]&&vis[x][y]==false)
  48.                   {
  49.                     q.emplace(x,y);
  50.                     vis[x][y]=true;
  51.                   }
  52.              }
  53.         }
  54.     }
  55. };

 六、扫雷游戏（重点）

. - 力扣（LeetCode）

         这题用dfs不需要标记数组，而用bfs需要用到标记数组，因为深度优先会将一个方格能扩展的都给扩展了，此时都在数组中会进行修改，但是广度优先是先把要扩展的全都丢进队列，然后再一个个处理，所以bfs需要一个标记数组来帮助我们。 

  1. class Solution {
  2. public:
  3.     int dx[8]={0,0,1,-1,1,1,-1,-1};
  4.     int dy[8]={1,-1,0,0,1,-1,1,-1}; //周围的八个方向
  5.     int m,n;
  6.     vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
  7.        m=board.size(),n=board[0].size();
  8.        int x=click[0],y=click[1];
  9.        if(board[x][y]=='M') board[x][y]='X';
  10.        else bfs(board,x,y);//不是雷，就向外扩展
  11.        return board;
  12.     }
  13.     void bfs(vector<vector<char>>& board,int i,int j)
  14.     {
  15.       queue<pair<int,int>> q;
  16.       vector<vector<bool>> vis(m,vector<bool>(n));//标记数组
  17.       q.emplace(i,j);
  18.       vis[i][j]=true;
  19.       while(!q.empty())
  20.       {
  21.         auto[a,b]=q.front();
  22.         q.pop();
  23.         int count=0;//数雷
  24.         for(int k=0;k<8;++k)
  25.         {
  26.             int x=dx[k]+a,y=dy[k]+b;
  27.             if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='M') ++count;
  28.         }
  29.         if(count) board[a][b]='0'+count;
  30.         else
  31.         {
  32.             //如果是B的话，需要将相邻的都丢到队列中
  33.             board[a][b]='B';
  34.             for(int k=0;k<8;++k)
  35.             {
  36.             int x=dx[k]+a,y=dy[k]+b;
  37.             if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='E'&&vis[x][y]==false) 
  38.             {
  39.                 q.emplace(x,y);
  40.                 vis[x][y]=true;
  41.             }
  42.           }
  43.         }
  44.       }
  45.     }
  46. };

七、衣柜整理

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     const int dx[2]={1,0};
  4.     const int dy[2]={0,1};
  5.     bool vis[100][100];
  6.     int m,n,cnt;
  7.     int wardrobeFinishing(int _m, int _n, int _cnt) {
  8.         m=_m,n=_n,cnt=_cnt;
  9.         int ret=0;//统计需要整理的格子
  10.         queue<pair<int,int>> q;
  11.         q.emplace(0,0);
  12.         vis[0][0]=true;
  13.         while(!q.empty())
  14.         {
  15.             auto[a,b]=q.front();
  16.             q.pop();
  17.             ++ret;
  18.             for(int k=0;k<2;++k)
  19.             {
  20.                 int x=dx[k]+a,y=dy[k]+b;
  21.                 if(x<m&&y<n&&vis[x][y]==false&&check(x,y)) 
  22.                  {
  23.                     q.emplace(x,y);
  24.                     vis[x][y]=true;
  25.                  }
  26.             }
  27.         }
  28.         return ret;
  29.     }
  30.     //检查这个格子能否整理
  31.     bool check(int i,int j)
  32.     {
  33.         int temp=0;
  34.         while(i)
  35.         {
  36.             temp+=(i%10);
  37.             i/=10;
  38.         }
  39.          while(j)
  40.         {
  41.             temp+=(j%10);
  42.             j/=10;
  43.         }
  44.         return temp<=cnt;
  45.     }
  46. };

 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号