130. Surrounded Regions

[Henrietta888]

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example, X X X X X O O X X X O X X O X X After running your function, the board should be:

X X X X X X X X X X X X X O X X

[Henrietta888]

当前未知，需要底层推导当前状态时，适合用DFS 当前已知，需要当前推导底层状态时，适合用BFS 此题目如果用DFS会导致堆栈溢出，解题思路： 首先，遍历最外层，找出O，标记O为F(说明我们已经处理过)，坐标入队列； 然后，遍历队列，寻找目标O的邻居（上下左右），已处理过的、X均忽略，若为O，标记为F，坐标入队列； 最后，剩下的O说明是没有出路的，需要替换为X，遍历数组，把O变为X，把F变为O；

public class Solution130V1 {
    public static final char X = 'X';
    public static final char O = 'O';
    public static final char F = 'F';
    private Queue<Point> q = new ArrayDeque<>();
    class Point {
        protected int x;
        protected int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public void solve(char[][] board) {
        if (board == null || board.length < 3 || board[0].length < 3) {
            return;
        }

        //flag
        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            for (int j = 0; j < chars.length; j++) {
                char aChar = chars[j];
                if (i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1) {
                    if (aChar == O) {
                        chars[j] = F;
                        q.add(new Point(i, j));
                    }
                }
            }
        }

        //handle
        while (q.size() > 0) {
            Point point = q.poll();
            int x = point.x, y = point.y;
            //top
            handleElement(board, x - 1, y);
            //right
            handleElement(board, x, y + 1);
            //bottom
            handleElement(board, x + 1, y);
            //left
            handleElement(board, x, y - 1);
        }

        //flag back
        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            for (int j = 0; j < chars.length; j++) {
                char aChar = chars[j];
                if (aChar == O) {
                    chars[j] = X;
                } else if (aChar == F) {
                    chars[j] = O;
                }

            }
        }

    }

    private void handleElement(char[][] board, int x, int y) {
        if (x > -1 && y > -1 && x < board.length && y < board[0].length) {
            char aChar = board[x][y];
            if(aChar==O){
                board[x][y]=F;
                q.add(new Point(x, y));
            }
        }
    }
}

[Henrietta888]

60 / 60 test cases passed. Status: Accepted Runtime: 8 ms