Surrounded Regions#

Given a 2D matrix containing X and O.
Find all the areas surrounded by X and replace all the O in these areas with X.
The surrounded areas do not exist on the boundary, in other words, any O on the boundary will not be replaced by X. Any O that is not on the boundary or not connected to the O on the boundary will eventually be replaced by X. If two elements are adjacent in the horizontal or vertical direction, they are considered connected.

Example#

After running your function, the matrix becomes:

Explanation#

The surrounded areas do not exist on the boundary, in other words, any O on the boundary will not be replaced by X. Any O that is not on the boundary or not connected to the O on the boundary will eventually be replaced by X. If two elements are adjacent in the horizontal or vertical direction, they are considered connected.

Solution#

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    var m = board.length;
    if(m === 0) return void 0;
    var n = board[0].length;
    var dfs = function(x, y){
        if(x<0 || y<0 || x>=m || y>=n || board[x][y] !== 'O') return void 0;
        board[x][y] = 'A';
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    }

    for (let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (let i = 1; i < n - 1; i++) {
        dfs(0, i);
        dfs(m - 1, i);
    }
    for (let i = 0; i < m; i++) {
        for (let k = 0; k < n; k++) {
            if (board[i][k] == 'A') board[i][k] = 'O';
            else if (board[i][k] == 'O') board[i][k] = 'X';
        }
    }
    return void 0;
};

Idea#

It is noticed from the explanation that any O on the boundary will not be replaced by X, which means all O ultimately connected to the boundary will not be replaced by X. Pay attention to the definition of connected, if two elements are adjacent in the horizontal or vertical direction, they are considered connected. According to the explanation, we need to find all the O on the border, and then do a deep recursion to search for all the O connected to this O, and then replace this O with another character, here we replace it with A, and then replace all the existing O in the matrix with X, i.e. the O that needs to be replaced because they are surrounded, and then replace all the A back to O. First, get the number of rows and columns of the matrix as m and n, then define the dfs function to do a recursive depth-first search. If the passed index is invalid or the value is not O, return, otherwise define the value as A, then do a depth-first search in four directions, and mark the connected O as A as well. Next, do a recursive depth-first search on the border of the matrix, and mark all the O connected to the border O as A. Finally, traverse the matrix, replace all the existing O with X, which is the O that needs to be replaced because they are surrounded, and then replace all the A back to O.

Daily question#

Reference#