洪水填充
基本介绍
洪水填充是一种很简单的技巧，设置路径信息进行剪枝和统计，类似感染的过程
路径信息不撤销，来保证每一片的感染过程可以得到区分
看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致
岛屿数量
题目链接
https://leetcode.cn/problems/number-of-islands/
思路分析
遇到一个 1，岛屿数量加一，把与其相连的所有 1 都感染了（dfs 的过程），被感染的点改为 0
dfs 中如果碰到了之前已经打过标记的点，直接返回，并不会展开，这里做了剪枝
时间复杂度：O（n * m）
代码实现
java
class Solution {
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int islands = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 遇到 1，将与其相连的点都感染了，改为 0，岛屿数量加一
if (grid[i][j] == '1') {
islands++;
dfs(grid, n, m, i, j);
}
}
}
return islands;
}
public void dfs(char[][] grid, int n, int m, int i, int j) {
// 越界，之前访问过，直接返回，不处理
if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != '1') {
return;
}
// grid[i][j] = '1'
grid[i][j] = '0';
// 上
dfs(grid, n, m, i - 1, j);
// 下
dfs(grid, n, m, i + 1, j);
// 左
dfs(grid, n, m, i, j - 1);
// 右
dfs(grid, n, m, i, j + 1);
}
}被围绕的区域
题目链接
https://leetcode.cn/problems/surrounded-regions/
思路分析
要求岛中被包围的部分，可以先从四周往中间遍历，把那些不被包围的岛屿（与边界相连的岛屿）打上标记，剩余部分就是被包围的，最后再将之前打的标记去掉即可
代码实现
java
class Solution {
public void solve(char[][] board) {
int n = board.length;
int m = board[0].length;
// 上下两行往中间遍历
for (int j = 0; j < m; j++) {
// 上边行
if (board[0][j] == 'O') {
dfs(board, n, m, 0, j);
}
// 下边行
if (board[n - 1][j] == 'O') {
dfs(board, n, m, n - 1, j);
}
}
// 左右两列往中间遍历，注意有一部分点在之前已经处理了
for (int i = 1; i < n - 1; i++) {
if (board[i][0] == 'O') {
dfs(board, n, m, i, 0);
}
if (board[i][m - 1] == 'O') {
dfs(board, n, m, i, m - 1);
}
}
// 撤销之前打过的标记，处理被包围的岛屿
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 被包围的岛屿，根据题意设置为 X
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
// 与边界相连的岛屿，撤销之前打的标记
if (board[i][j] == 'F') {
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board, int n, int m, int i, int j) {
// 越界，之前被打过标记了，不处理
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O') {
return;
}
// 处理与边界相连岛屿，打上标记
board[i][j] = 'F';
// 上
dfs(board, n, m, i + 1, j);
// 下
dfs(board, n, m, i - 1, j);
// 左
dfs(board, n, m, i, j - 1);
// 右
dfs(board, n, m, i, j + 1);
}
}最大人工岛
题目链接
https://leetcode.cn/problems/making-a-large-island/
思路分析
先给每一块岛屿打上标记，然后讨论每个 0 位置变成 1 后于周围的岛屿相接会不会使得岛屿最大
⚠️ 注意：需要考虑特殊情况，如果所有点都是 1，则最大岛就是整个二维矩阵
代码实现
java
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int id = 2;
// 首先给每一片岛屿打标记
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
dfs(grid, n, m, i, j, id++);
}
}
}
// 统计每一片岛屿的数量
int[] sizes = new int[id];
// 考虑特殊情况，如果岛屿全是 1，在打标记中就会被处理为 2
// 经过计算，ans 即为矩阵的面积，在后续步骤中不会进入 dfs
// 直接返回 ans，否则 ans 维持的就是最大岛的大小，在后续
// 进入 dfs 后，讨论每个点改变为 1 后是否会带来更大的岛屿
// 不断更新最大岛屿的数值，直到 dfs 结束后，返回 ans
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] > 1) {
ans = Math.max(ans, ++sizes[grid[i][j]]);
}
}
}
// 每个岛屿不能重复计算，设置 visited 数组
boolean[] visited = new boolean[id];
// 讨论每个 0 位置，变成 1 之后是否带来更大的岛屿
int up, down, left, right, merge;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) {
// 讨论上下左右四个方向是否越界，取出对应的值
up = i > 0 ? grid[i - 1][j] : 0;
down = i + 1 < n ? grid[i + 1][j] : 0;
left = j > 0 ? grid[i][j - 1] : 0;
right = j + 1 < m ? grid[i][j + 1] : 0;
// 先标记 up 方向，再讨论其他方向
visited[up] = true;
// 当前点 + 下方岛屿的大小
merge = 1 + sizes[up];
if (!visited[down]) {
merge += sizes[down];
visited[down] = true;
}
if (!visited[left]) {
merge += sizes[left];
visited[left] = true;
}
if (!visited[right]) {
merge += sizes[right];
visited[right] = true;
}
// 更新答案
ans = Math.max(ans, merge);
// 讨论下一个 0，不同 0 之间互不影响
visited[up] = false;
visited[down] = false;
visited[left] = false;
visited[right] = false;
}
}
}
return ans;
}
public void dfs(int[][] grid, int n, int m, int i, int j, int id) {
// 越界，之前标记过，直接返回
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != 1) {
return;
}
// 给每一块岛屿打标记，用于区分不同的岛屿
grid[i][j] = id;
// 上
dfs(grid, n, m, i + 1, j, id);
// 下
dfs(grid, n, m, i - 1, j, id);
// 左
dfs(grid, n, m, i, j + 1, id);
// 右
dfs(grid, n, m, i, j - 1, id);
}
}⭐ 打砖块
题目链接
https://leetcode.cn/problems/bricks-falling-when-hit/
思路分析
将所有炮弹位置 -1
将天花板的所有元素感染
⭐ 时光倒流技巧，从后往前遍历炮弹
（1）将炮弹位置 +1，如果发现是 0，说明炮弹打空了，无需处理
（2）如果发现炮弹位置的四周存在天花板或者炮弹位置就在天花板，把与其相连的元素都感染，计算新增感染元素的个数
（3）掉落元素的个数 = 新增感染元素个数 - 1，减一是因为炮弹位置的元素被击碎了，才导致元素的掉落，被击碎的元素并不会掉落
代码实现
java
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
int n = grid.length;
int m = grid[0].length;
int[] ans = new int[hits.length];
// 特判，如果只有天花板元素，不会有元素掉落
if (n == 1) {
return ans;
}
// 第一步；将炮弹位置减一
for (int[] hit : hits) {
grid[hit[0]][hit[1]]--;
}
// 第二步：将天花板元素都感染
for (int i = 0; i < m; i++) {
dfs(grid, n, m, 0, i);
}
// 第三步：时光倒流
// （1）从后往前遍历炮弹，将炮弹位置 +1
// （2）根据 worth 函数判断该位置是否值得 dfs
for (int i = hits.length - 1; i >= 0; i--) {
int row = hits[i][0];
int col = hits[i][1];
grid[row][col]++;
if (worth(grid, n, m, row, col)) {
// 注意减一，炮弹位置被击碎，掉落的元素是与其相连的元素
ans[i] = dfs(grid, n, m, row, col) - 1;
}
}
return ans;
}
// 返回被感染元素的个数
public int dfs(int[][] grid, int n, int m, int i, int j) {
// 越界，之前标记过，不处理
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != 1) {
return 0;
}
// 打标记
grid[i][j] = 2;
// 从 [i,j] 位置开始，被感染的元素个数 = [i,j] 这个点 + 四周与其相连的元素
return 1 + dfs(grid, n, m, i - 1, j)
+ dfs(grid, n, m, i + 1, j)
+ dfs(grid, n, m, i, j - 1)
+ dfs(grid, n, m, i, j + 1);
}
// 判断是否值得遍历，前提是该位置的是 1
// （1）周围存在天花板元素
// （2）该元素在天花板位置
public boolean worth(int[][] grid, int n, int m, int i, int j) {
return grid[i][j] == 1 &&
(i == 0 || i > 0 && grid[i - 1][j] == 2
|| i < n - 1 && grid[i + 1][j] == 2
|| j > 0 && grid[i][j - 1] == 2
|| j < m - 1 && grid[i][j + 1] == 2);
}
}