leetcode：130. 被围绕的区域（bfs）

偏执的太偏执、 2021-09-28 10:58 289阅读 0赞

package BFS;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /*
    给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
    找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
    示例:
    X X X X
    X O O X
    X X O X
    X O X X
    运行你的函数后，矩阵变为：
    X X X X
    X X X X
    X X X X
    X O X X
     */
    public class Solve130BFS {
        private boolean[][] juge = new boolean[1000][1000];
    
        public void solve(char[][] board) {
            if (board.length - 1 <= 0 || board[0].length <= 0) return;
            int m = board.length - 1;
            int n = board[0].length - 1;
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (board[i][j] == 'O' && !juge[i][j])
                        bfs(i, j, board, m, n);
                }
            }
    
        }
    
        public void bfs(int x, int y, char[][] board, int m, int n) {
            List<int[]> jugehuan = new ArrayList<>();
            boolean isHuan = false;
            //能改变的方向四个
            int[][] change = {
       {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
            //bfs队列
            Queue<int[]> q = new LinkedList<>();
            int[] one = {x, y};
            //扫描到的第一个0进入队列
            q.add(one);
            board[x][y] = 'X';
            juge[x][y] = true;
            while (!q.isEmpty()) {
                int[] nowxy = q.poll();
                jugehuan.add(nowxy);
                for (int i = 0; i < 4; i++) {
                    int changex = nowxy[0] + change[i][0];
                    int changey = nowxy[1] + change[i][1];
                    if (changex >= 1 && changex < m && changey >= 1 && changey < n) {
                        if (board[changex][changey] == 'O') {
                            int[] now = {changex, changey};
                            q.add(now);
                            board[changex][changey] = 'X';
                            juge[changex][changey] = true;
                        }
                    } else {
                        if (board[changex][changey] == 'O')
                            isHuan = true;
                    }
                }
            }
            if (isHuan) {
                for (int i = 0; i < jugehuan.size(); i++) {
                    board[jugehuan.get(i)[0]][jugehuan.get(i)[1]] = 'O';
                }
            }
        }
    
        public static void main(String[] args) {
            Solve130BFS s = new Solve130BFS();
            char[][] a = {
                    {'X', 'X', 'X'},
                    {'X', 'O', 'X'},
                    {'X', 'X', 'X'}
            };
            s.solve(a);
        }
    }