DFS & Flood-Filling

Surrounded Regions

• 标准的DFS题

• 先从四周往里走，找到O,说明围不死，改成'*'

• from outer to inner, find all 'O' in the boundary

• mark it as '' and dfs

• then do a for loop, replace 'O' with 'X', replace '' with 'O'

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '*') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};
    private void dfs(char[][] board, int row, int col) {
        int m = board.length, n = board[0].length;
        board[row][col] = '*';
        for (int i = 0; i < 4; i++) {
            int x = row + dX[i];
            int y = col + dY[i];
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') continue;
            dfs(board, x, y);
        }
    }
}