算法奇妙屋(十三)-BFS解决FloodFill问题

    int[] x = new int[]{-1, 1, 0, 0};
    int[] y = new int[]{0, 0, -1, 1};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        Queue<int[]> q = new LinkedList<>();
        int tmp = image[sr][sc];
        if (tmp == color) {
            return image;
        }
        int m = image.length;
        int n = image[0].length;
        q.offer(new int[]{sr,sc});
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            image[a][b] = color;
            for (int i = 0; i < 4; i++) {
                int tx = a + x[i];
                int ty = b + y[i];
                if (tx >= 0 && tx < m && ty >= 0 && ty < n && image[tx][ty] == tmp) {
                    q.offer(new int[]{tx, ty});
                }
            }
        }
        return image;
    }

    int[] x = new int[] { -1, 1, 0, 0 };
    int[] y = new int[] { 0, 0, -1, 1 };

    public int numIslands(char[][] grid) {
        int ret = 0;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] f = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !f[i][j]) {
                    q.offer(new int[]{i,j});
                    fun(grid, q, f, m, n);
                    ret++;
                }
            }
        }
        return ret;
    }

    void fun(char[][] grid, Queue<int[]> q, boolean[][] f, int m, int n) {
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0];
            int b = t[1];
            for (int i = 0; i < 4; i++) {
                int tx = a + x[i];
                int ty = b + y[i];
                if (tx >= 0 && tx < m && ty >= 0 && ty < n && grid[tx][ty] == '1' && !f[tx][ty]) {
                    f[tx][ty] = true;
                    q.offer(new int[]{tx, ty});
                }
            }
        }
    }

    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    boolean[][] f;
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        f = 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 && !f[i][j]) {
                    int count = fun(grid, i, j, m, n);
                    ret = Math.max(ret, count);
                }
            }
        }
        return ret;
    }
    int fun(int[][] grid, int i, int j, int m, int n) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        int count = 1;
        while (!q.isEmpty()) {
            f[i][j] = true;
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int p = 0; p < 4; p++) {
                int x = a + dx[p];
                int y = b + dy[p];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !f[x][y]) {
                    q.offer(new int[]{x, y});
                    f[x][y] = true;
                    count++;
                }
            }
        }
        return count;
    }

    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{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' ) {
                fib(board, i, 0);
            }
            if (board[i][n - 1] == 'O' ) {
                fib(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O' ) {
                fib(board, 0, j);
            }
            if (board[m - 1][j] == 'O' ) {
                fib(board, m - 1, 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';
                }
            }
        }
    }
    void fib(char[][] board, int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0];
            int b = t[1];
            board[a][b] = '*';
            for (int p = 0; p < 4; p++) {
                int x = a + dx[p];
                int y = b + dy[p];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' ) {
                    q.offer(new int[]{x, y});
                    board[x][y] = '*';
                }
            }
        }
    }