当前位置：首页 > article >正文

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

article 2024/11/15 4:52:58

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

查看全文

http://www.kler.cn/a/308161.html