😮130 surrounded regions

https://leetcode.com/problems/surrounded-regions/

难点主要是如果按正常的bfs或者dfs你不到最后或者进行到一半不知道是不是有node在边界上(escape了)，所以先找出边界上的node从它们先遍历一遍再说

class Solution {
    private int[][] DIR = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0, true);
            }
            if (board[i][n -1] == 'O') {
                bfs(board, i, n - 1, true);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                bfs(board, 0, j, true);
            }
            if (board[m - 1][j] == 'O') {
                bfs(board, m - 1, j, true);
            }
        }
        
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    bfs(board, i, j, false);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'E') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void bfs(char[][] board, int i, int j, boolean escape) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(i, j));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (board[node.x][node.y] != 'O') {
                continue;
            }
            if (escape) {
                board[node.x][node.y] = 'E';
            } else {
                board[node.x][node.y] = 'X';
            }
            for (int[] dir : DIR) {
                int nx = node.x + dir[0];
                int ny = node.y + dir[1];
                if (isValid(board, nx, ny)) {
                    queue.offer(new Node(nx, ny));
                }
            }
        }
    }
    private boolean isValid(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        if (i >= 0 && i < m && j >= 0 && j < n) {
            return true;
        }
        return false;
    }
}