130.Surrounded Regions

1-DFS

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

First, check the four border of the matrix. If there is a element is
’O’, alter it and all its neighbor ‘O’ elements to ‘1’.

• Then ,alter all the ‘O’ to ‘X’

• At last,alter all the ‘1’ to ‘O’

class Solution {
    public void solve(char[][] board) {
        if(board.length < 1)
            return;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            dfs(board, i, 0, directions);
            if(n > 1)
                dfs(board, i, n - 1, directions);
        }
        for(int i = 0; i < n; i++){
            dfs(board, 0, i, directions);
            if(m > 1)
                dfs(board, m - 1, i, directions);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == '+')
                    board[i][j] = 'O';
            }
        }

        return;
    }
    public void dfs(char[][] board, int i, int j, int[][] directions){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length)
            return;
        if(board[i][j] == 'O'){
            board[i][j] = '+';
            for(int[] dir : directions){
                int newX = i + dir[0];
                int newY = j + dir[1];
                dfs(board, newX, newY, directions);
            }
        }
    }
}