LeetCode(130) -- Surrounded Regions

Problem

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.

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

My Solution

从每个点（不包括四条边）开始扩展，如果最后接到边，就标记上需要修改，然后重新跑一遍dfs修改。这样比较慢。

class Solution {
    int r = 0, c = 0;
    char[][] board;
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        this.board = board;
        r = board.length;
        c = board[0].length;
        for (int i = 1; i < r - 1; i++) {
            for (int j = 1; j < c - 1; j++) {
                if (dfs(i, j)) {
                    flip(i, j, false);
                } else {
                    flip(i, j, true);
                }
            }
        }
    }
    
    public boolean dfs(int i, int j) {
        if (i == 0 || j == 0 || i == r - 1 || j == c - 1) {
            if (board[i][j] == 'O') {
                return true;
            } else {
                return false;
            }
        }
        if (board[i][j] == 'X' || board[i][j] == '-') {
            return false;
        }
        board[i][j] = '-';
        if (dfs(i - 1, j) || dfs(i + 1, j) || dfs(i, j - 1) || dfs(i, j + 1)) {
            return true;
        }
        return false;
    }
    
    public void flip(int i, int j, boolean toX) {
        if (i == 0 || j == 0 || i == r - 1 || j == c - 1 || board[i][j] != '-') {
            return;
        }
        if (toX) {
            board[i][j] = 'X';
        } else {
            board[i][j] = 'O';
        }
        flip(i - 1, j, toX);
        flip(i + 1, j, toX);
        flip(i, j - 1, toX);
        flip(i, j + 1, toX);
    }
}

The Best Solution

还是从四个边开始，要保留的都换成C，最后再整体扫一遍，把C全变成O, 把O全变成X.

class Solution {
    int r = 0, c = 0;
    char[][] board;
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        // 第一列和最后一列起始的"O"区域都换成"C"
        for (int i = 0; i < board.length; i++) {
            floodFill(board, 'O', 'C', i, 0);
            floodFill(board, 'O', 'C', i, board[i].length - 1);
        }
        // 第一行和最后一行起始的"O"区域都换成"C"
        for (int j = 0; j < board[0].length; j++) {
            floodFill(board, 'O', 'C', 0, j);
            floodFill(board, 'O', 'C', board.length - 1, j);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'C') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void floodFill(char[][] board, char oldChar, char newChar, int i, int j) {
        if (i == board.length || j == board[0].length || i == -1 || j == -1 || board[i][j] != oldChar) {
            return;
        }
        board[i][j] = newChar;
        floodFill(board, oldChar, newChar, i - 1, j);
        floodFill(board, oldChar, newChar, i + 1, j);
        floodFill(board, oldChar, newChar, i, j - 1);
        floodFill(board, oldChar, newChar, i, j + 1);
    }
}