32.递归、搜索、回溯之floodfill算法

0.简介

1.图像渲染

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m, n;int prev;public int[][] floodFill(int[][] image, int sr, int sc, int color) {if (image[sr][sc] == color)return image;m = image.length;n = image[0].length;prev = image[sr][sc];dfs(image, sr, sc, color);return image;}public void dfs(int[][] image, int i, int j, int color) {image[i][j] = color;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {dfs(image, x, y, color);}}}
}

2.岛屿数量

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {boolean[][] vis;int m, n;int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == '1') {ret++;dfs(grid, i, j);}}return ret;}public void dfs(char[][] grid, int i, int j) {vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') {dfs(grid, x, y);}}}
}

3.岛屿的最大面积

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {boolean[][] vis;int m, n;int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, i, j);ret = Math.max(ret, count);}}return ret;}public void dfs(int[][] grid, int i, int j) {count++;vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)dfs(grid, x, y);}}
}

4.被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

题目解析

算法原理

代码

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;// 1. 先把边界的 O 相连的联通块，全部修改成 '.'for (int j = 0; j < n; j++) {if (board[0][j] == 'O')dfs(board, 0, j);if (board[m - 1][j] == 'O')dfs(board, m - 1, j);}for (int i = 0; i < m; i++) {if (board[i][0] == 'O')dfs(board, i, 0);if (board[i][n - 1] == 'O')dfs(board, i, n - 1);}// 2. 还原for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (board[i][j] == '.')board[i][j] = 'O';else if (board[i][j] == 'O')board[i][j] = 'X';}}public void dfs(char[][] board, int i, int j) {board[i][j] = '.';for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {dfs(board, x, y);}}}
}

5.太平洋大西洋水流问题

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {int m, n;int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public List<List<Integer>> pacificAtlantic(int[][] h) {m = h.length;n = h[0].length;boolean[][] pac = new boolean[m][n];boolean[][] atl = new boolean[m][n];// 1. 先处理 pac 洋for (int j = 0; j < n; j++)dfs(h, 0, j, pac);for (int i = 0; i < m; i++)dfs(h, i, 0, pac);// 2. 再处理 atl 洋for (int i = 0; i < m; i++)dfs(h, i, n - 1, atl);for (int j = 0; j < n; j++)dfs(h, m - 1, j, atl);// 3. 提取结果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> tmp = new ArrayList<>();tmp.add(i);tmp.add(j);ret.add(tmp);}return ret;}public void dfs(int[][] h, int i, int j, boolean[][] vis) {vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j]) {dfs(h, x, y, vis);}}}
}

6.扫雷问题

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {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) {m = board.length;n = board[0].length;int x = click[0], y = click[1];if (board[x][y] == 'M') // 如果直接点到地雷，游戏结束{board[x][y] = 'X';return board;}dfs(board, x, y);return board;}public void dfs(char[][] board, int i, int j) {// 统计⼀下周围地雷的个数int count = 0;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] == 'M') {count++;}}if (count == 0) // 周围没有地雷{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(board, x, y);}}} else {board[i][j] = (char) ('0' + count);return;}}
}

7.机器人的运动范围

. - 力扣（LeetCode）

题目解析

算法原理

代码

class Solution {int m, n, k;boolean[][] vis;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int ret;public int movingCount(int _m, int _n, int _k) {m = _m;n = _n;k = _k;vis = new boolean[m][n];dfs(0, 0);return ret;}public void dfs(int i, int j) {ret++;vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y)) {dfs(x, y);}}}public boolean check(int i, int j) {int tmp = 0;while (i != 0) {tmp += i % 10;i /= 10;}while (j != 0) {tmp += j % 10;j /= 10;}return tmp <= k;}
}