Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

 

class Solution {
    static int rows, cols;
    public void solve(char[][] board) {
    if (board == null || board.length == 0) return ;
     
   rows = board.length;
    cols = board[0].length;
   
    for (int i = 0; i < rows; i++) {
        dfs(board, i, 0);
        dfs(board, i, cols - 1);
    }
    for (int j = 0; j < cols; j++) {
        dfs(board, 0, j);
        dfs(board, rows - 1, j);
    }

    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (board[i][j] == 'O') board[i][j] = 'X';
        if (board[i][j] == 'A') board[i][j] = 'O';
      }
    }
  }

  protected void dfs(char[][] board, int row, int col) {
    if(row < 0 || row > this.rows - 1 || col < 0 || col > this.cols - 1 || board[row][col] != 'O') return ;

    board[row][col] = 'A';
    dfs(board, row, col + 1);
    dfs(board, row + 1, col);
    dfs(board, row, col - 1);
    dfs(board, row - 1, col);
  }
}

Try it on Leetcode

Here, we are going to solve the problem using DFS(Depth First Search).  If you read the small explanation above the solution, you can easily come up with the solution.

Hint for solving this problem:

[We are going to iterate all borders and changing 'O' with different alphablet i.e., 'A', this can be achieved using DFS. Finally, we are replacing remaining interior 'O' with 'X' and 'A' with 'O']

1) Run DFS on first row, last row, first column, last column and replace all 'O' with 'A'.

2) Replace all remaining 'O' with 'X'

3) Finally replace 'A' with 'O'.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

Subscribe us to receive updates instantly.

Please let us know about your views in comment section.

Happy Coding...😍