Surrounded Regions

Problem

Given an m x n matrix grid containing only characters 'X' and 'O', modify grid to replace all regions of 'O' that are completey surrounded by 'X' with 'X'.

A region of 'O' is surrounded by 'X' if there is no adjacent path (cells that border each other in the N, W, E, S directions) consisting of only 'O' from anywhere inside that region to the border of the board.

Input:

grid = [
["X","X","X","X","O"],
["X","X","O","X","X"],
["X","X","O","X","O"],
["X","O","X","X","X"]
["X","O","X","X","X"]
]

Output:

[
["X","X","X","X","O"],
["X","X","X","X","X"],
["X","X","X","X","O"],
["X","O","X","X","X"],
["X","O","X","X","X"]
]

Explanation: The region of O’s at grid[1][2] and grid[2][2] is completely surrounded, so we replace them with X’s. All the other “O”s are connected to the border by a path of all “O”s, so we leave them as is.

Input:

grid = [
["O","O"],
["O","X"],
]

Output:

[
["O", "O"],
["O", "X"]
]

Explanation: All the “O”s are connected to the border.

Explanation

In order to solve this problem, we can first recognize that there are two types of “Os” in the grid, those that are reachable on a path of connected “O”s starting from the border of the grid, and those that are not.

The “Os” that are reachable from the border are the ones that we want to keep, while the “Os” that are not reachable from the border are the ones that we want to change to “Xs”.

In order for an “O” to be reachable from the border, it must be connected to an “O” that is on the border. This means that we can start from each cell in the border of the grid and use depth-first search to find all the “Os” that are reachable from the border of the grid (by following a path of connected “Os” in the N, E, S, W directions). Whenever we find an “O” that is reachable from the border, we can change its value to “S” to mark it as safe.

After marking them as safe, we can then iterate through each cell in the grid and change the “Os” that are not marked as safe to “Xs”, while also changing the “safe” cells back to “Os”.

class Solution:
    def surrounded_regions(self, grid): 
        if not grid:
            return grid
        
        rows = len(grid)
        cols = len(grid[0])

        # recursive function to find all the "O"s that are reachable
        # from the border and mark them as "S"
        def dfs(x, y):
            # return immediately if the cell is out of bounds or is not an "O
            if x < 0 or y < 0 or x >= rows or y >= cols or grid[x][y] != 'O':
                return
            grid[x][y] = 'S'

            # explore the neighboring cells
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)

        # initialize the dfs for the first and last column
        for i in range(rows):
            if grid[i][0] == 'O':
                dfs(i, 0)
            if grid[i][cols - 1] == 'O':
                dfs(i, cols - 1)

         # initialize the dfs for the first and last row
        for j in range(cols):
            if grid[0][j] == 'O':
                dfs(0, j)
            if grid[rows - 1][j] == 'O':
                dfs(rows - 1, j)

        # change the "O"s that are not marked as "S" to "X"s and the "S"s back to "O"s
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 'O':
                    grid[i][j] = 'X'
                elif grid[i][j] == 'S':
                    grid[i][j] = 'O'
                    
        return grid

class Solution {
    public void surroundedRegions(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;

        // initialize the dfs for the first and last column
        for (int i = 0; i < rows; i++) {
            if (grid[i][0] == 'O') {
                dfs(grid, i, 0, rows, cols);
            }
            if (grid[i][cols - 1] == 'O') {
                dfs(grid, i, cols - 1, rows, cols);
            }
        }

        // initialize the dfs for the first and last row
        for (int j = 0; j < cols; j++) {
            if (grid[0][j] == 'O') {
                dfs(grid, 0, j, rows, cols);
            }
            if (grid[rows - 1][j] == 'O') {
                dfs(grid, rows - 1, j, rows, cols);
            }
        }

        // change the "O"s that are not marked as "S" to "X"s and the "S"s back to "O"s
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 'O') {
                    grid[i][j] = 'X';
                } else if (grid[i][j] == 'S') {
                    grid[i][j] = 'O';
                }
            }
        }
    }
    
    // recursive function to find all the "O"s that are reachable
    // from the border and mark them as "S"
    private void dfs(char[][] grid, int x, int y, int rows, int cols) {
        // return immediately if the cell is out of bounds or is not an "O"
        if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] != 'O') {
            return;
        }
        grid[x][y] = 'S';

        // explore the neighboring cells
        dfs(grid, x + 1, y, rows, cols);
        dfs(grid, x - 1, y, rows, cols);
        dfs(grid, x, y + 1, rows, cols);
        dfs(grid, x, y - 1, rows, cols);
    }
}

func surroundedRegions(grid [][]byte) {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return
    }
    
    rows := len(grid)
    cols := len(grid[0])

    var dfs func(x, y int)
    dfs = func(x, y int) {
        // return immediately if the cell is out of bounds or is not an "O"
        if x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] != 'O' {
            return
        }
        grid[x][y] = 'S'

        // explore the neighboring cells
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
    }

    // initialize the dfs for the first and last column
    for i := 0; i < rows; i++ {
        if grid[i][0] == 'O' {
            dfs(i, 0)
        }
        if grid[i][cols - 1] == 'O' {
            dfs(i, cols - 1)
        }
    }

    // initialize the dfs for the first and last row
    for j := 0; j < cols; j++ {
        if grid[0][j] == 'O' {
            dfs(0, j)
        }
        if grid[rows - 1][j] == 'O' {
            dfs(rows - 1, j)
        }
    }

    // change the "O"s that are not marked as "S" to "X"s and the "S"s back to "O"s
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == 'O' {
                grid[i][j] = 'X'
            } else if grid[i][j] == 'S' {
                grid[i][j] = 'O'
            }
        }
    }
}

class Solution {
    surroundedRegions(grid: string[][]): string[][] {
        if (!grid || grid.length === 0) {
            return grid;
        }
        
        const rows = grid.length;
        const cols = grid[0].length;

        // recursive function to find all the "O"s that are reachable
        // from the border and mark them as "S"
        function dfs(x: number, y: number): void {
            // return immediately if the cell is out of bounds or is not an "O"
            if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] !== 'O') {
                return;
            }
            grid[x][y] = 'S';

            // explore the neighboring cells
            dfs(x + 1, y);
            dfs(x - 1, y);
            dfs(x, y + 1);
            dfs(x, y - 1);
        }

        // initialize the dfs for the first and last column
        for (let i = 0; i < rows; i++) {
            if (grid[i][0] === 'O') {
                dfs(i, 0);
            }
            if (grid[i][cols - 1] === 'O') {
                dfs(i, cols - 1);
            }
        }

        // initialize the dfs for the first and last row
        for (let j = 0; j < cols; j++) {
            if (grid[0][j] === 'O') {
                dfs(0, j);
            }
            if (grid[rows - 1][j] === 'O') {
                dfs(rows - 1, j);
            }
        }

        // change the "O"s that are not marked as "S" to "X"s and the "S"s back to "O"s
        for (let i = 0; i < rows; i++) {
            for (let j = 0; j < cols; j++) {
                if (grid[i][j] === 'O') {
                    grid[i][j] = 'X';
                } else if (grid[i][j] === 'S') {
                    grid[i][j] = 'O';
                }
            }
        }
                    
        return grid;
    }
}

Keeping Track of Visited Cells

In the above solution, marking each cell as “S” also serves to keep track of the visited cells. We only make recursive calls to the neighboring cells if the current cell is an “O”. This way, we avoid visiting the same cell multiple times, as a cell that was previously “O” but is now “S” will not be visited again.