数据结构与算法：洪水填充

前言

洪水填充是一种用在图上的搜刮算法，其过程就像洪水或病毒一样徐徐蔓延整个地区，继而到达遍历和统计相同属性的连通地区的功能，中间也可以通过每走过一个节点就设置路径信息的方法来到达剪枝的效果。
一、岛屿数目——洪水填充方法

1. class Solution {
2. public:
4.     int numIslands(vector<vector<char>>&grid)
5.     {
6.         return solve2(grid);
7.     }
9.     //洪水填充方法
11.     int solve2(vector<vector<char>>&grid)
12.     {
13.         int n=grid.size();
14.         int m=grid[0].size();
16.         int ans=0;
17.         for(int i=0;i<n;i++)
18.         {
19.             for(int j=0;j<m;j++)
20.             {
21.                 if(grid[i][j]=='1')
22.                 {
23.                     dfs(i,j,grid);
24.                     ans++;
25.                 }
26.             }
27.         }
29.         return ans;
30.     }
32.     void dfs(int i,int j,vector<vector<char>>&grid)
33.     {
34.         if(i<0||i==grid.size()||j<0||j==grid[0].size()||grid[i][j]!='1')
35.         {
36.             return ;
37.         }
39.         grid[i][j]=0;
40.         dfs(i,j+1,grid);
41.         dfs(i,j-1,grid);
42.         dfs(i+1,j,grid);
43.         dfs(i-1,j,grid);
44.     }
46.     //并查集方法
48.     vector<int>father;
49.     int sets;
51.     int solve1(vector<vector<char>>& grid) {
52.         int n=grid.size();
53.         int m=grid[0].size();
55.         build(n,m,grid);
57.         for(int i=0;i<n;i++)
58.         {
59.             for(int j=0;j<m;j++)
60.             {
61.                 if(grid[i][j]=='1')
62.                 {
63.                     if(j>0&&grid[i][j-1]=='1')//左
64.                     {
65.                         Union(index(i,j,m),index(i,j-1,m));
66.                     }
67.                     if(i>0&&grid[i-1][j]=='1')//上
68.                     {
69.                         Union(index(i,j,m),index(i-1,j,m));
70.                     }
71.                 }
72.             }
73.         }
74.         return sets;
75.     }
77.     void build(int n,int m,vector<vector<char>>&grid)
78.     {
79.         father.resize(n*m);
80.         sets=0;
81.         int idx;
82.         //只有为“1”的格子才计算
83.         for(int i=0;i<n;i++)
84.         {
85.             for(int j=0;j<m;j++)
86.             {
87.                 if(grid[i][j]=='1')
88.                 {
89.                     idx=index(i,j,m);
90.                     father[idx]=idx;
91.                     sets++;
92.                 }
93.             }
94.         }
95.     }
97.     int find(int i)
98.     {
99.         if(i!=father[i])
100.         {
101.             father[i]=find(father[i]);
102.         }
103.         return father[i];
104.     }
106.     void Union(int x,int y)
107.     {
108.         int fx=find(x);
109.         int fy=find(y);
110.         if(fx!=fy)
111.         {
112.             father[fx]=fy;
113.             sets--;
114.         }
115.     }
117.     int index(int i,int j,int m)
118.     {
119.         return i*m+j;
120.     }
121. };

复制代码

 这个题如果看过我上一篇文章数据结构与算法：并查集的话对这个题应该不陌生，除了可以用并查集，还可以用洪水填充做。
根据洪水填充的过程，观察标题就可以发现，当出现一个“1”时，就开始洪水填充，感染所有连通的地区，相称于遍历完了一整个岛屿，所以要把所有点都改成0，然后让ans++即可。
这里洪水填充的函数接纳了dfs（深度优先搜刮）方法，固然也可以改成广度优先。如果没有越界大概碰到“水”，就先修改当前点为0，然后去上下左右感染。
二、被围绕的地区

1. class Solution {
2. public:
3.     void solve(vector<vector<char>>& board) {
4.         int n=board.size();
5.         int m=board[0].size();
7.         //先感染边界‘O’，画出不能修改的
8.         for(int j=0;j<m;j++)
9.         {
10.             if(board[0][j]=='O')
11.             {
12.                 dfs(0,j,board);
13.             }
14.             if(board[n-1][j]=='O')
15.             {
16.                 dfs(n-1,j,board);
17.             }
18.         }
19.         for(int i=0;i<n;i++)
20.         {
21.             if(board[i][0]=='O')
22.             {
23.                 dfs(i,0,board);
24.             }
25.             if(board[i][m-1]=='O')
26.             {
27.                 dfs(i,m-1,board);
28.             }
29.         }
31.         //修改被包围的‘O’
32.         for(int i=0;i<n;i++)
33.         {
34.             for(int j=0;j<m;j++)
35.             {
36.                 if(board[i][j]=='O')
37.                 {
38.                     board[i][j]='X';
39.                 }
40.                 if(board[i][j]=='F')
41.                 {
42.                     board[i][j]='O';
43.                 }
44.             }
45.         }
46.     }
48.     void dfs(int i,int j,vector<vector<char>>&board)
49.     {
50.         if(i<0||i==board.size()||j<0||j==board[0].size()||board[i][j]!='O')
51.         {
52.             return ;
53.         }
55.         board[i][j]='F';
56.         dfs(i-1,j,board);
57.         dfs(i+1,j,board);
58.         dfs(i,j-1,board);
59.         dfs(i,j+1,board);
60.     }
61. };

复制代码

 这个题就需要一点预处理了，由于界限处是默认无法被困绕的，所以上来先顺着界限摸一遍，感染在界限位置无法被困绕的“O”。那么之后出现的“O”就都是可以被困绕的了，就遍历整个格子，有“O”就改成“X”，然后由于之前把界限处“O”改成了“F”，所以需要改回来。
三、最大人工岛

1. class Solution {
2. public:
3.     int largestIsland(vector<vector<int>>& grid) {
4.         int n=grid.size();
6.         //设置编号
7.         int id=2;
8.         for(int i=0;i<n;i++)
9.         {
10.             for(int j=0;j<n;j++)
11.             {
12.                 if(grid[i][j]==1)
13.                 {
14.                     dfs(i,j,grid,id++);
15.                 }
16.             }
17.         }
19.         //统计大小
20.         map<int,int>size;
21.         int ans=0;
22.         for(int i=0;i<n;i++)
23.         {
24.             for(int j=0;j<n;j++)
25.             {
26.                 if(grid[i][j]>1)
27.                 {
28.                     ans=max(ans,++size[grid[i][j]]);
29.                 }
30.             }
31.         }
33.         //遍历‘0’
34.         vector<bool>visited(id,false);//去重
35.         int up,down,left,right,sum;
36.         for(int i=0;i<n;i++)
37.         {
38.             for(int j=0;j<n;j++)
39.             {
40.                 if(grid[i][j]==0)
41.                 {   
42.                     up=i==0?0:grid[i-1][j];
43.                     down=i==n-1?0:grid[i+1][j];
44.                     left=j==0?0:grid[i][j-1];
45.                     right=j==n-1?0:grid[i][j+1];
46.                     visited[up]=true;
47.                     sum=size[up]+1;
48.                     if(!visited[down])
49.                     {
50.                         sum+=size[down];
51.                         visited[down]=true;
52.                     }
53.                     if(!visited[left])
54.                     {
55.                         sum+=size[left];
56.                         visited[left]=true;
57.                     }
58.                     if(!visited[right])
59.                     {
60.                         sum+=size[right];
61.                         visited[right]=true;
62.                     }
63.                     ans=max(ans,sum);
64.                     visited[up]=false;
65.                     visited[down]=false;
66.                     visited[left]=false;
67.                     visited[right]=false;
68.                 }
69.             }
70.         }
72.         return ans;
73.     }
75.     void dfs(int i,int j,vector<vector<int>>&grid,int id)
76.     {
77.         if(i<0||i==grid.size()||j<0||j==grid[0].size()||grid[i][j]!=1)
78.         {
79.             return ;
80.         }
82.         grid[i][j]=id;
83.         dfs(i-1,j,grid,id);
84.         dfs(i+1,j,grid,id);
85.         dfs(i,j-1,grid,id);
86.         dfs(i,j+1,grid,id);
87.     }
88. };

复制代码

 这个题就需要点思考了，首先分析标题可以想出整体思路就是先统计已经是岛屿的地区，接着再遍历每一个“0”，去看周围是否有岛屿。
接着就是分步解决题目，首先是统计已经是岛屿的地区，这个就是碰到是“1”的点洪水填充即可。但由于之后再遍历“0”的时间要获取周围岛屿的巨细，所以要知道每一个岛屿本身的巨细，所以考虑在洪水填充时给每个岛屿打上编号，接着设置一个map存岛屿编号对应巨细。需要注意的是，由于最后让返回最大岛屿的巨细，当情况是原装岛就是最大的时，要返回原装岛的巨细，所以在这一步就要统计ans最大值。
之后是遍历“0”的过程，由于当一个“0”周围存在同一片岛屿时，这个岛屿的巨细加一次就够了，所以还要考虑去重。具体方法就是设置一个visited数组，来到就设为true。之后遍历，每次统计周围岛屿的巨细之和即可。
四、打砖块

1. class Solution {
2. public:
3.     vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
4.         //思想————“时光倒流”->炮弹倒着看->之前炮弹对当前有影响
6.         int n=grid.size();
7.         int m=grid[0].size();
8.         int h=hits.size();
9.         vector<int>ans(h,0);
10.         
11.         //特例
12.         if(n==1)
13.         {
14.             return ans;
15.         }
17.         //先让命中位置-1
18.         for(int i=0;i<h;i++)
19.         {
20.             grid[hits[i][0]][hits[i][1]]--;
21.         }
23.         //天花板
24.         for(int j=0;j<m;j++)
25.         {
26.             if(grid[0][j]==1)
27.             {
28.                 dfs(0,j,grid);
29.             }
30.         }
32.         //“时光倒流”
33.         for(int i=h-1;i>=0;i--)
34.         {
35.             grid[hits[i][0]][hits[i][1]]++;//命中位置补回来
36.             if(worth(hits[i][0],hits[i][1],n,m,grid))
37.             {
38.                 ans[i]=dfs(hits[i][0],hits[i][1],grid)-1;
39.             }
40.         }
42.         return ans;
43.     }
45.     //返回新增的安全格子数
46.     int dfs(int i,int j,vector<vector<int>>&grid)
47.     {
48.         if(i<0||i==grid.size()||j<0||j==grid[0].size()||grid[i][j]!=1)
49.         {
50.             return 0;
51.         }
53.         grid[i][j]=2;
54.         return 1+dfs(i-1,j,grid)+dfs(i+1,j,grid)+dfs(i,j-1,grid)+dfs(i,j+1,grid);
55.     }
57.     //是否值得填充
58.     bool worth(int i,int j,int n,int m,vector<vector<int>>&grid)
59.     {
60.         return grid[i][j]==1&&  //有效命中
61.         (i==0||   //在天花板上
62.         (i>0&&grid[i-1][j]==2)||(i<n-1&&grid[i+1][j]==2)||(j>0&&grid[i][j-1]==2)||
63.         (j<m-1&&grid[i][j+1]==2));  //周围有“2”
64.     }
65. };

复制代码

 这个题的思路就非常巧妙了，属于是初见肯定想不到的那种。
分析标题，由于之前的炮弹对当前的炮弹有影响，换言之，能让下面全部掉落的炮弹一定是最后一发，前面与之干系的炮弹可以明白为都是辅助炮，那么这里可以用到一个头脑——“时光倒流”。“时光倒流”的方法就是，先只遍历一遍炮弹的命中位置，接着从后往前看炮弹，统计掉落的砖块。
所以首先只遍历炮弹命中位置，让该位置-1即可。
之后，考虑天花板处连接的砖块，直接连接天花板的砖块洪水填充即可。
经历上述过程后，肯定有剩余的“1”，这些就是会被炮弹打下来的砖块，所以此时进行“时光倒流”。首先把命中位置补回来，接下来的worth函数表示是否值得去洪水填充，即满足打中的是砖块且要么在天花板，可以连接下面的砖块，要么周围有“2”，即和天花板连接的砖块，那么就可以去洪水填充。由于要统计数目，所以这里的dfs函数需要返回连通砖块的个数，所以只需要返回附近之和再加本身的1即可。注意标题形貌被命中的砖块不算，所以ans要再减去1。
总结

其实感觉洪水填充和并查集有异曲同工之处，就像这几个题感觉都能改并查集，只是洪水填充会更快。而且洪水填充只在情况比较简朴的标题里速度比并查集快，劈面对上一篇里最后感染源头那种题时的发挥空间就比较有限了，所以这里就更体现出并查集给集合打标签的这个用法的优势了。
还剩不到一个月，要加快速度了啊！期待接下来的图论和动态规划章节！！
END


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。