算法【洪水填充】

洪水填充是一种很简单的技巧，设置路径信息进行剪枝和统计，类似感染的过程。路径信息不撤销，来保证每一片的感染过程可以得到区分。看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致。

下面通过一些题目来加深理解。

题目一

测试链接：https://leetcode.cn/problems/number-of-islands/

分析：洪水填充更可以看作是一个感染过程，将空间中符合条件的位置感染成我们需要的东西。这道题可以从是陆地的地方深度优先开始感染，将陆地感染成用以区分不再是陆地的信号。当遍历完整个空间后，我们就知道有多少个岛屿。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int row, int column, vector<vector<char>>& grid){if(i < 0 || i >= row || j < 0 || j >= column || grid[i][j] != '1'){return;}grid[i][j] = '0';for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], row, column, grid);}}int numIslands(vector<vector<char>>& grid) {int row = grid.size();int column = grid[0].size();int ans = 0;for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){if(grid[i][j] == '1'){++ans;dfs(i, j, row, column, grid);}}}return ans;}
};

其中，arr数组是用于遍历一个位置的周围即上下左右；在numIslands方法中调用dfs方法时，岛屿数加1，相当于重新感染一个新岛屿。

题目二

测试链接：https://leetcode.cn/problems/surrounded-regions/

分析：这个题可以看出，如果一个O和矩阵的四周存在的O相连，则这个O不会被替换成X，那么我们可以对矩阵的四周，也就是上下左右四个边界的O，使用深度优先进行感染，将其设为一个用以区分的信号。最后将矩阵中所有没有被更新为信号的O，更新为X；将更新为信号的位置更新为O。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int row, int column, vector<vector<char>>& board){if(i < 0 || i >= row || j < 0 || j >= column || board[i][j] != 'O'){return;}board[i][j] = 'z';for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], row, column, board);}}void solve(vector<vector<char>>& board) {int row = board.size();int column = board[0].size();for(int i = 0;i < column;++i){if(board[0][i] == 'O'){dfs(0, i, row, column, board);}}for(int i = 0;i < column;++i){if(board[row-1][i] == 'O'){dfs(row-1, i, row, column, board);}}for(int i = 0;i < row;++i){if(board[i][0] == 'O'){dfs(i, 0, row, column, board);}}for(int i = 0;i < row;++i){if(board[i][column-1] == 'O'){dfs(i, column-1, row, column, board);}}for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){if(board[i][j] == 'O'){board[i][j] = 'X';}else if(board[i][j] == 'z'){board[i][j] = 'O';}}}}
};

其中，信号为z，也就是说在最后更新时，O更新为X，z更新为O；最开始的4个for循环是对上下左右四个边界的O进行感染。

题目三

测试链接：https://leetcode.cn/problems/making-a-large-island/

分析：这道题涉及到岛屿的面积，所以在感染时，我们设置的信号应该是岛屿的编号。这样方便对不同编号的岛屿进行面积统计。在感染之后，我们得到了岛屿的数量，以及每个岛屿的面积。这时，遍历空间中那些不是岛屿的位置并进行判定。判定过程为对这些位置上下左右是否连接了岛屿，如果连接了，则加上这个岛屿的面积，注意不要重复计算岛屿面积，最后再加上这个位置的面积，也就是再加1。遍历空间中不是岛屿的位置，最终得到最大值。代码如下。

class Solution {
public:int area[125003] = {0};set<int> used;int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int n, vector<vector<int>>& grid, int number){if(i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1){return;}grid[i][j] = number;++area[number];for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], n, grid, number);}}int largestIsland(vector<vector<int>>& grid) {int n = grid.size();int number = 2;int ans = 0;int temp_ans;for(int i = 0;i < n;++i){for(int j = 0;j < n;++j){if(grid[i][j] == 1){dfs(i, j, n, grid, number);++number;}}}for(int i = 2;i < number;++i){ans = ans > area[i] ? ans : area[i];}for(int i = 0;i < n;++i){for(int j = 0;j < n;++j){if(grid[i][j] == 0){temp_ans = 0;for(int index = 0;index < 4;++index){if(i+arr[index] >= 0 && i+arr[index] < n && j+arr[index+1] >= 0 && j+arr[index+1] < n &&grid[i+arr[index]][j+arr[index+1]] != 0 && used.count(grid[i+arr[index]][j+arr[index+1]]) == 0){temp_ans += area[grid[i+arr[index]][j+arr[index+1]]];used.insert(grid[i+arr[index]][j+arr[index+1]]);}}++temp_ans;ans = ans > temp_ans ? ans : temp_ans;used.clear();}}}return ans;}
};

其中，used用来判断一个岛屿是否已经被加过；number是当前岛屿的编号，因为0和1已经被使用所以number从2开始；需要将ans的初始值设为最大岛屿值是因为有可能全部是陆地，也就是没有连接的机会，那么这时的最大值自然就是最大岛屿值。

题目四

测试链接：https://leetcode.cn/problems/bricks-falling-when-hit/

分析：这个题我们看到了稳定和掉落这两个状态，很容易想到使用并查集。使用并查集的思路是，在没有打落砖块的时候，使用并查集将稳定的砖块设为一个集合，不稳定的砖块设为一个集合。最开始顶部的砖块是稳定的，然后相邻砖块之间归为一个集合。设置一个是否稳定的数组，顶部砖块是稳定的设为true，其他设为false。在union方法合并的时候，更新代表元素的是否稳定数组。遍历完砖块后，查询有多少个砖块的集合的代表元素是稳定的，这时候得到没有打入炮弹时的稳定砖块数目。实际上这个数目应该是统计的砖块数目。然后每打落一个砖块，重新统计一次稳定的数目，然后用上一次稳定的数目减此次稳定的数目再减1，因为打落的砖块是消失不计入不稳定的数目，但是这个方法复杂度太高，会超时。所以使用洪水填充加时光倒流。我们需要得到每次炮弹掉落的砖块数目，那么可以在所有炮弹打落之后往回加，也就是从最后一个炮弹开始，每一个炮弹没打之后多了多少稳定的砖块。主要流程就是，首先，将所有炮弹打出去，也就是把炮弹的指向位置的网格值减1，然后将顶部的网格，也就是已经稳定的网格开始洪水填充现存的砖块，将网格值更新为2（什么都行主要要区分1），然后开始时光倒流，从最后一个炮弹往前遍历，把炮弹指向位置处加1，如果为0，则代表之前这个位置没有砖块，continue；如果大于0，则判定这个位置的上下左右是否有等于2的砖块，因为2代表了现在稳定的砖块，如果有，则从炮弹恢复的位置开始洪水填充将1更新为2，更新的数目减1则为这个炮弹对应掉落的砖块数目，减1是因为炮弹指向位置不计入掉落的砖块数目。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};int dfs(int i, int j, int row, int column, vector<vector<int>>& grid){if(i < 0 || i >= row || j < 0 || j >= column || grid[i][j] != 1){return 0;}int num = 1;grid[i][j] = 2;for(int index = 0;index < 4;++index){num += dfs(i+arr[index], j+arr[index+1], row, column, grid);}return num;}vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {vector<int> ans;int row = grid.size();int column = grid[0].size();int length = hits.size();ans.assign(length, 0);for(int i = 0;i < length;++i){--grid[hits[i][0]][hits[i][1]];}for(int i = 0;i < column;++i){if(grid[0][i] == 1){dfs(0, i, row, column, grid);}}for(int i = length-1;i >= 0;--i){++grid[hits[i][0]][hits[i][1]];if(grid[hits[i][0]][hits[i][1]] == 0){continue;}if(hits[i][0] == 0){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0] >= 0 && hits[i][0] < row && hits[i][1]+1 >= 0 && hits[i][1]+1 < column && grid[hits[i][0]][hits[i][1]+1] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0] >= 0 && hits[i][0] < row && hits[i][1]-1 >= 0 && hits[i][1]-1 < column && grid[hits[i][0]][hits[i][1]-1] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0]+1 >= 0 && hits[i][0]+1 < row && hits[i][1] >= 0 && hits[i][1] < column && grid[hits[i][0]+1][hits[i][1]] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0]-1 >= 0 && hits[i][0]-1 < row && hits[i][1] >= 0 && hits[i][1] < column && grid[hits[i][0]-1][hits[i][1]] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}}return ans;}
};

其中，在恢复炮弹指向位置时大于0的判定中，如果指向位置本身就是顶部位置，那么不管这个位置的上下左右是否有为2的位置，直接填充。