FloodFill 算法 专题

一. 图像渲染

图像渲染

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

二. 岛屿数量

岛屿数量

class Solution {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };boolean[][] vis;int m, n;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 (grid[i][j] == '1' && !vis[i][j]) {vis[i][j] = true;dfs(grid, i, j);ret++;}}}return ret;}public void dfs(char[][] g, int i, int j) {for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && g[x][y] == '1' && !vis[x][y]) {vis[x][y] = true;System.out.println("(" + x + "," + y + ")");dfs(g, x, y);}}}
}

三. 岛屿的最大面积

岛屿的最大面积

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

四. 被围绕的区域

被围绕的区域

class Solution {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;public void solve(char[][] board) {m = board.length;n = board[0].length;//先把边界与'O'相连的块修改成'.'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);}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);}//把'.' 修改成'X', 把'O' 修改成'X'for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O') board[i][j] ='X';if(board[i][j] == '.') board[i][j] = 'O';}}}public void dfs(char[][] board, int i, int j){board[i][j] = '.';for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'O'){dfs(board, x, y);}}}
}

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

太平洋大西洋水流问题

class Solution {List<List<Integer>> ret;int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;public List<List<Integer>> pacificAtlantic(int[][] heights) {ret = new ArrayList<>();m = heights.length;n = heights[0].length;boolean[][] pac = new boolean[m][n];boolean[][] atl = new boolean[m][n];//正难则反//找出从太平洋反方向流能流到哪些位置//太平洋for(int i = 0; i < m; i++){if(!pac[i][0])  dfs(heights, i, 0, pac);}for(int j = 0; j < n; j++){if(!pac[0][j])  dfs(heights, 0, j, pac);}//找出从大西洋反方向流能流到哪些位置//大西洋for(int i = 0; i < m; i++){if(!atl[i][n - 1])  dfs(heights, i, n - 1, atl);}for(int j = 0; j < n; j++){if(!atl[m - 1][j])  dfs(heights, m - 1, j, atl);}//这些位置的交集就是我们要的答案for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(pac[i][j] && atl[i][j]) {List<Integer> path = new ArrayList<>();path.add(i);path.add(j);ret.add(path);} }}return ret;}public void dfs(int[][] h, int i, int j, boolean[][] vis){int tmp = h[i][j];vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && h[x][y] >= h[i][j]){dfs(h, x, y, vis);}}}
}

六. 扫雷游戏

扫雷游戏

class Solution {int m, n;int[] dx = { 0, 0, 1, -1, 1, 1, -1, -1 };int[] dy = { 1, -1, 0, 0, -1, 1, 1, -1 };public char[][] updateBoard(char[][] board, int[] click) {m = board.length;n = board[0].length;int i = click[0];int j = click[1];if (board[i][j] == 'M') {board[i][j] = 'X';return board;}dfs(board, i, j);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];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && 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];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'E') {dfs(board, x, y);}}}else{//如果周围有地雷, 则直接改成地雷数board[i][j] =(char)(count + '0');}}
}

七. 衣橱整理

衣橱整理

class Solution {int ret;int[] dx = {0, 1};int[] dy = {1, 0};int m ,n;boolean[][] vis;public int wardrobeFinishing(int _m, int _n, int cnt) {m = _m;n = _n;vis = new boolean[m][n];dfs(0, 0, cnt);return ret;}public void dfs(int i, int j, int cnt){ret++;vis[i][j] = true;for(int k = 0; k < 2; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && y >= 0 && x < m && y < n && check(x, y, cnt) && !vis[x][y]){dfs(x, y, cnt);}}}public boolean check(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;}if(sum <= cnt) return true;return false;}
}