130. Surrounded Regions

[huimeich]

Given a 2D board containing 'X' and '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

[huimeich]

public class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] == 'O') {
                dfsMark(board, i, 0);
            }
            if (board[i][board[0].length-1] == 'O') {
                dfsMark(board, i, board[0].length-1);
            }
        }
        for (int i = 0; i < board[0].length; i++) {
            if (board[0][i] == 'O') {
                dfsMark(board, 0, i);
            }
            if (board[board.length-1][i] == 'O') {
                dfsMark(board, board.length-1, i);
            }
        }
        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';
            }
        }
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'T') board[i][j] = 'O';
            }
        }
    }
    public void dfsMark(char[][] board, int row, int col){
        if (board[row][col] == 'O') {
            board[row][col] = 'T';
            if (row > 0 && board[row-1][col] == 'O') dfsMark(board, row - 1, col);
            if (row < board.length-2 && board[row+1][col] == 'O') dfsMark(board, row + 1, col);
            if (col < board[0].length-2 && board[row][col + 1] == 'O') dfsMark(board, row, col + 1);
            if (col > 0 && board[row][col-1] == 'O') dfsMark(board, row, col - 1);
        }
    }
}