Depth-First Search
Surrounded Regions
DESCRIPTION (inspired by Leetcode.com)
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.
public class Solution {
public String[][] surrounded_regions(String[][] grid) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
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 {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 columnfor (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 rowfor (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"sfor (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 cellsdfs(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);}}
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.
What is the time complexity of this solution?
O(m * n)
O(N + Q)
O(4ⁿ)
O(log n)