[LeetCode 130] Surrounded Region

Solution

1. 首先对matrix四个边的O，将所有与其相连的O全部置为Y （这是需要保留的O）
2. 然后再对matrix扫描一次，将所有的O全部置为X
3. 再扫描一次，将所有的Y全部置为X，这样就得到了结果。

设置value的时候用DFS，对checkValue的四个方向都分别都设置为setValue

• 如果row， col超出边界，直接返回
• 如果当前row, col已经访问过，直接返回
• 如果当前board [row][col] != checkValue, 直接返回
• 否则，对当前cell的四个方向继续进行迭代DFS设置。

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board [0].length == 0)
            return;
        
        //1. scan the boarder (only boarder) of the matrix, for each of the O, use DFS to set all connected O to Y
        boolean[][] visited = new boolean [board.length][board [0].length];
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board [0].length; j++) {
                if (i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) {
                    solveHelper (board, visited, i, j, 'O', '*');
                }
            }
        }
        
        //2. scan the matrix again, to set all O to X
        visited = new boolean [board.length][board [0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board [0].length; j++) {
                solveHelper (board, visited, i, j, 'O', 'X');
            }
        }
        
        //3. scan the matrix again, to set all * back to X
        visited = new boolean [board.length][board [0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board [0].length; j++) {
                solveHelper (board, visited, i, j, '*', 'O');
            }
        }
    }
    
    public void solveHelper (char[][] board, boolean[][] visited, int row, int col, char checkValue, char setValue) {
        // base case1:
        if (row < 0 || row >= board.length || col < 0 || col >= board [0].length)
            return;
        // base case 2:
        if (board [row][col] != checkValue)
            return;
        
        // base case 3:
        if (visited [row][col])
            return;
        
        
        visited [row][col] = true;
        board [row][col] = setValue;
        int[][] directions = {{0,1}, {1,0}, {-1,0}, {0,-1}};
        
        for (int[] direction : directions) {
            solveHelper (board, visited, row + direction[0], col + direction[1], checkValue, setValue);
        }
        
        //visited[row][col] = false;
        
    }
}