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;
}
}