阅读量:0
Floodfill，翻译为洪水灌溉，而floodfill算法本质上是为了解决在矩阵中性质相同的联通块问题。
一、图像渲染
与dfs一样，从指定的起点开始向四个方向扩展，区别就是用之前通过参数将下标关系传递给dfs，而现在是将下标关系的键值对传给queue。
class Solution { public: //定义4个方向 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; typedef pair<int,int> PII; vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { //采用BFS算法解决floodfill算法， 解决相同性质的矩阵联通块问题 int prev=image[sr][sc]; if(prev==color) return image; int m=image.size(),n=image[0].size(); queue<PII> q;//队列 q.emplace(sr,sc); while(!q.empty()) { //先修改当前位置 auto [a,b]=q.front();//c++14的玩法 q.pop(); image[a][b]=color;//修改成color for(int k=0;k<4;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&& image[x][y]==prev) q.emplace(x,y); } } return image; } };二、岛屿数量
1. 因为要计算岛屿的数量，所以我们每进行一次bfs就要统计一下该岛屿，因为我们可以将bfs单独封装成一个函数。
2.在扩展的时候，我们需要标记我们扩展过的网格，这里有两种方案：
（1）修改值，但是修改值会改变原数据，必须要想办法修改回来。
（2）标记数组（常用），相同大小的标记数组，将探索过的网格标记为true
class Solution { public: int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; typedef pair<int,int> PII; int m,n;//因为要单独封装一个BFS bool check[301][301];//标记数组 看看哪些点是选过的 int numIslands(vector<vector<char>>& grid) { //ret统计一共有多少个联通块 int ret=0; //直接修改原数组的话 可能会有问题 m=grid.size(); n=grid[0].size(); for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(grid[i][j]=='1'&&check[i][j]==false) { ++ret; bfs(grid,i,j); } return ret; } void bfs(vector<vector<char>>& grid,int i,int j) { queue<PII> q;//队列统计下标实现BFS q.emplace(i,j); check[i][j]=true; while(!q.empty()) { auto [a,b]=q.front(); q.pop(); for(int k=0;k<4;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&check[x][y]==false) { q.emplace(x,y); check[x][y]=true; } } } } };三、岛屿的最大面积
我们需要统计每个岛屿的大小，所以我们可以将bfs单独封装成一个函数，然后利用他的返回值返回岛屿的大小，在主函数中去更新找到最大值。
class Solution { public: int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; typedef pair<int,int> PII; int m,n;//因为要单独封装一个BFS bool check[50][50];//标记数组 看看哪些点是选过的 int maxAreaOfIsland(vector<vector<int>>& grid) { int ret=0;//统计最大岛屿数量 m=grid.size(),n=grid[0].size(); for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(grid[i][j]==1&&check[i][j]==false) ret=max(bfs(grid,i,j),ret); return ret; } int bfs(vector<vector<int>>& grid,int i,int j) { queue<PII> q; q.emplace(i,j); check[i][j]=true; int count=1; while(!q.empty()) { auto [a,b]=q.front(); q.pop(); for(int k=0;k<4;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&check[x][y]==false) { check[x][y]=true; q.emplace(x,y); ++count; } } } return count; } };四、被围绕的区域
如果直接做的话，我们会发现如果我们处理一个区域的时候一旦触碰到边界，那么就全部需要回头。或者说得先遍历一遍，确认这个联通块没有触碰边界，然后再遍历一次去标记，这样显然效率是很低的。因此我们的解决方案就是正难则反。
（1）先从边界走一波bfs，将O全部修改成 .
（2）然后遍历矩阵（遍历矩阵的时候可以顺便还原，所以这个地方我们就不需要设置标记数组），将剩下的O修改成X，然后将.还原成O。
class Solution { public: const int dx[4]={1,-1,0,0}; const int dy[4]={0,0,1,-1}; typedef pair<int,int> PII; int m,n;//因为要单独封装一个BFS void solve(vector<vector<char>>& board) { m=board.size(),n=board[0].size(); //先处理第一行和最后一行 for(int j=0;j<n;++j) { if(board[0][j]=='O') bfs(board,0,j); if(board[m-1][j]=='O') bfs(board,m-1,j); } //处理第一列和最后一列 for(int i=0;i<m;++i) { if(board[i][0]=='O') bfs(board,i,0); if(board[i][n-1]=='O') bfs(board,i,n-1); } //进行复原 for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(board[i][j]=='O') board[i][j]='X'; else if(board[i][j]=='.') board[i][j]='O'; } void bfs(vector<vector<char>>& board,int i,int j) { queue<PII> q; q.emplace(i,j); board[i][j]='.'; while(!q.empty()) { auto [a,b]=q.front(); q.pop(); for(int k=0;k<4;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O') { q.emplace(x,y); board[x][y]='.'; } } } } };五、太平洋大西洋水流问题
如果我们直接做的话，显然需要需要遍历矩阵，然后每遍历一个点就要判断该点是否可以同时流向太平洋和大西洋，显然这样是十分麻烦的。因此我们的思路就是正难则反。
（1）从矩阵的边界开始逆推（从低往高处流）
（2）用两个标记数组进行标记，一个标记表示可以流向太平洋，另一个标记可以流向大西洋，最后我们将两个标记数组都标记过的坐标进行统计并返回即可。
class Solution { public: const int dx[4]={0,0,-1,1}; const int dy[4]={1,-1,0,0}; int m,n; vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) { //正难则反 用两个标记数组，用边界去往中间走，将能走的位置给标记了 //最后两个标记数组都被标记的地方就是我们最终的结果 m=h.size(),n=h[0].size(); //定义两个标记数组 vector<vector<bool>> atl(m,vector<bool>(n)); auto pac=atl; //先探索行 for(int i=0;i<m;++i) { bfs(h,i,0,pac); bfs(h,i,n-1,atl); } //探索列 for(int j=0;j<n;++j) { bfs(h,0,j,pac); bfs(h,m-1,j,atl); } //遍历一下 如果标记数组都存在，就返回结果 vector<vector<int>> ret; for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(pac[i][j]&&atl[i][j]) ret.push_back({i,j}); return ret; } void bfs(vector<vector<int>>& h,int i,int j,vector<vector<bool>>&vis) { queue<pair<int,int>> q; q.emplace(i,j); vis[i][j]=true; while(!q.empty()) { auto [a,b]=q.front(); q.pop(); for(int k=0;k<4;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&h[x][y]>=h[a][b]&&vis[x][y]==false) { q.emplace(x,y); vis[x][y]=true; } } } } };六、扫雷游戏（重点）
这题用dfs不需要标记数组，而用bfs需要用到标记数组，因为深度优先会将一个方格能扩展的都给扩展了，此时都在数组中会进行修改，但是广度优先是先把要扩展的全都丢进队列，然后再一个个处理，所以bfs需要一个标记数组来帮助我们。
class Solution { public: int dx[8]={0,0,1,-1,1,1,-1,-1}; int dy[8]={1,-1,0,0,1,-1,1,-1}; //周围的八个方向 int m,n; vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { m=board.size(),n=board[0].size(); int x=click[0],y=click[1]; if(board[x][y]=='M') board[x][y]='X'; else bfs(board,x,y);//不是雷，就向外扩展 return board; } void bfs(vector<vector<char>>& board,int i,int j) { queue<pair<int,int>> q; vector<vector<bool>> vis(m,vector<bool>(n));//标记数组 q.emplace(i,j); vis[i][j]=true; while(!q.empty()) { auto[a,b]=q.front(); q.pop(); int count=0;//数雷 for(int k=0;k<8;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='M') ++count; } if(count) board[a][b]='0'+count; else { //如果是B的话，需要将相邻的都丢到队列中 board[a][b]='B'; for(int k=0;k<8;++k) { int x=dx[k]+a,y=dy[k]+b; if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='E'&&vis[x][y]==false) { q.emplace(x,y); vis[x][y]=true; } } } } } };七、衣柜整理
class Solution { public: const int dx[2]={1,0}; const int dy[2]={0,1}; bool vis[100][100]; int m,n,cnt; int wardrobeFinishing(int _m, int _n, int _cnt) { m=_m,n=_n,cnt=_cnt; int ret=0;//统计需要整理的格子 queue<pair<int,int>> q; q.emplace(0,0); vis[0][0]=true; while(!q.empty()) { auto[a,b]=q.front(); q.pop(); ++ret; for(int k=0;k<2;++k) { int x=dx[k]+a,y=dy[k]+b; if(x<m&&y<n&&vis[x][y]==false&&check(x,y)) { q.emplace(x,y); vis[x][y]=true; } } } return ret; } //检查这个格子能否整理 bool check(int i,int j) { int temp=0; while(i) { temp+=(i%10); i/=10; } while(j) { temp+=(j%10); j/=10; } return temp<=cnt; } }; 
