FloodFill(洪水灌溉)算法专题——DFS深搜篇
目录
1、图像渲染
1.1 算法原理
1.2 算法代码
2、岛屿数量
2.1 算法原理
2.2 算法代码
3、岛屿的最大面积
3.1 算法原理
3.2 算法代码
4、被围绕的区域
4.1 算法原理
4.2 算法代码
5、太平洋大西洋水流问题
5.1 算法原理
5.2 算法代码
6、扫雷游戏
6.1 算法原理
6.2 算法代码
7、衣橱整理 （原：面试题 13. 机器人的运动范围 ）
7.1 算法原理
7.2 算法代码
1、图像渲染
. - 力扣（LeetCode）
1.1 算法原理
- 从(sr,sc)位置开始上下左右暴搜，将区域中符合条件的值修改为color。
- 细节问题：当 color == image[sr][sc]时，不需修改，直接返回即可。
1.2 算法代码
class Solution {int[] dx, dy;int[][] image;int color;int n, m;int val;public int[][] floodFill(int[][] image_, int sr, int sc, int color_) {if(color_ == image_[sr][sc]) return image_;image = image_;val = image[sr][sc];color = color_;n = image.length;m = image[0].length;dx = new int[]{-1, 1, 0, 0};dy = new int[]{0, 0, -1, 1};image[sr][sc] = color;dfs(sr, sc);return image;}public void dfs(int i, int j) {for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && image[x][y] == val) {image[x][y] = color;dfs(x, y);}}}
}2、岛屿数量
. - 力扣（LeetCode）
2.1 算法原理
全局变量：
- boolean[][] check;//是否来过
- int ret;//返回值
- int[] dx;//横坐标上下左右
- int[] dy;//纵坐标上下左右
思想：
- 遍历矩阵，每次来到新的'1'区域，将这个区域中的所有'1'位置做好标记(check置为false)，ret++
- 返回ret
2.2 算法代码
class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check;int ret;int m, n;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;check = new boolean[m][n];for(int i = 0; i < m ; i++) {for(int j = 0; j < n; j++) {if(check[i][j] == false && grid[i][j] == '1') {ret++;check[i][j] = true;dfs(grid, i, j);}}}return ret;}public void dfs(char[][] grid, int i, int j) {for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !check[x][y]) {check[x][y] = true;dfs(grid, x, y);}}}
}3、岛屿的最大面积
. - 力扣（LeetCode）
3.1 算法原理
与上题基本一致，选出面积最大值即可：
- 暴搜
- count记录每块陆地的最大面积(每次进入dfs，count++)
- ret记录所有陆地的最大面积(选出count的最大值)
3.2 算法代码
class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check;int ret;int m, n;int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;check = new boolean[m][n];for(int i = 0; i < m ; i++) {for(int j = 0; j < n; j++) {if(check[i][j] == false && grid[i][j] == 1) {count = 0;check[i][j] = true;dfs(grid, i, j);//统计一块陆地的面积ret = Math.max(ret, count);}}}return ret;}public void dfs(int[][] grid, int i, int j) {count++; for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y]) {check[x][y] = true;dfs(grid, x, y);}}}
}4、被围绕的区域
. - 力扣（LeetCode）
4.1 算法原理
本题采用“正难则反”法则，既然我们无法区分边缘区域与内部区域，那么就先对矩阵的边缘区域进行操作：
- 对边缘区域的所有'O'区域进行深搜，修改为'.'
- 此时边缘区域的'O'已全部修改为'.'，内部区域的'O'仍为'O'
- 再遍历整个矩阵，'.'重新修改为'O'(边缘区域的'O')，'O'则修改为'X'(内部区域的'O')
4.2 算法代码
class Solution {int m, n;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };public void solve(char[][] board) {m = board.length;n = board[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//把边缘区域的O置为.if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {board[i][j] = '.';dfs(board, i, j);}}}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';}}public void dfs(char[][] board, int i, int j) {for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {board[x][y] = '.';dfs(board, x, y);}}}
}5、太平洋大西洋水流问题
. - 力扣（LeetCode）
5.1 算法原理
本题仍采用“正难则反”原则：
- 从海岸反向记录可流入海洋的位置
- 分别标记哪些位置可流入太平洋（boolean[][] pac），可流入则标为true
- 分别标记哪些位置可流入大西洋（boolean[][] atl），可流入则标为true
- pac、atl中均为true的位置，说明均可流入两大海洋。
5.2 算法代码
class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int m, n;public List<List<Integer>> pacificAtlantic(int[][] heights) {m = heights.length;n = heights[0].length;boolean[][] pac = new boolean[m][n];//标记太平洋可流入的位置boolean[][] atl = new boolean[m][n];//标记大西洋可流入的位置//pacfor(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);//atlfor(int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);for(int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);//都可流入的位置List<List<Integer>> ret = new ArrayList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(pac[i][j] && atl[i][j]) {List<Integer> list = new ArrayList<>();list.add(i);list.add(j);ret.add(list);}}}return ret;}public void dfs(int[][] heights, int i, int j, boolean[][] check) {check[i][j] = true;int cur = heights[i][j];for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && heights[x][y] >= cur) {dfs(heights, x, y, check);}}}
}6、扫雷游戏
. - 力扣（LeetCode）
6.1 算法原理
本题主要节目就是dfs及回溯：如果相邻没有地雷的空方块被挖出，则将其上下左右及四角方向全部递归揭露所有和其相邻的未挖出的方块，直至相邻的方块的周围有地雷，则将周围有地雷的方块标为地雷的数量。
对于斜方向上，我们只需在dx和dy数组上的对应位置上加上相应值即可。
6.2 算法代码
class Solution {char[][] board;int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};int m, n;public char[][] updateBoard(char[][] board_, int[] click) {board = board_;m = board.length;n = board[0].length;int sx = click[0], sy = click[1];char ch = board[sx][sy];if(ch == 'M') {board[sx][sy] = 'X';return board;}if(ch == 'B') return board;dfs(sx, sy);return board;}public void dfs(int i, int j) {int count = 0;for(int k = 0; k < 8; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {count++;}}if(count != 0) {//周围有地雷board[i][j] = (char)(count + '0');return;}else {//周围没有地雷board[i][j] = 'B';for(int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {dfs(x, y);}}}}
}7、衣橱整理 （原：面试题 13. 机器人的运动范围 ）
. - 力扣（LeetCode）
7.1 算法原理
直接dfs洪水灌溉，需要注意的是:
- 每个位置不能重复进入
- 横纵下标的每个位的数值之和不能超过cnt
7.2 算法代码
class Solution {int ret;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int m, n;boolean[][] check;public int wardrobeFinishing(int m_, int n_, int cnt) {m = m_;n = n_;check = new boolean[m][n];dfs(0, 0, cnt);return ret;}public void dfs(int i, int j, int cnt) {check[i][j] = true;ret++;for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && isRight(x, y, cnt)) {dfs(x, y, cnt);}}}public boolean isRight(int x, int y, int cnt) {int sum = 0;while (x != 0) {sum += x % 10;x /= 10;}while (y != 0) {sum += y % 10;y /= 10;}return sum <= cnt;}
}END