Surrounded Regions

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

DFS:

We can solve this problem in 2 ways:
1. BFS
2. DFS

In this tutorial we solve it by using DFS.

The solution here is very simple. First we check if any of the edges of row and column is ‘o’ and also check if their neighbour is also ‘o’ then replace them with the character “1”.

Then we convert all the remaining ‘o’ to ‘x’ and replace ‘1’ with ‘o’. We get our solution.

The steps can be pictorially shown as below:

X X X X        X X X X            X X X X
X O O X  --->  X O O X   -then->  X X X X
X X O X        X X O X            X X X X
X O X X        X 1 X X            X O X X

/*
* File     : except_surrounded_regions.cpp
*/

#include<iostream>
#include<vector>
using namespace std;

//helper function
void check(vector<vector<char>>& board, int i, int j) 
{
        if (board[i][j] == 'O') 
        {
          // if the value is 'O' then replace it with '1'
            board[i][j] = '1';

            // check if its neighbors is also 'O' by recursively calling this function
            if (i > 1) check(board, i - 1, j);
            if (j > 1) check(board, i, j - 1);
            if (i + 1 < board.size()) check(board, i + 1, j);
            if (j + 1 < board[0].size()) check(board, i, j + 1);
        }
}


void solve_using_dfs(vector<vector<char>>& board) 
{
  if (board.empty()) return;

  int row = board.size();
  int col = board[0].size();

  // check for column
  for (int i = 0; i < row; ++i) 
  {
      check(board, i, 0);             // first column
      check(board, i, col - 1);       // last column
  }

  // check for rows
  for (int j = 1; j < col - 1; ++j) 
  {
      check(board, 0, j);             // first row
      check(board, row - 1, j);       // last row
  }

  // Now replace 'O' with 'X' and '1' with 'O'
  for (int i = 0; i < row; ++i)
      for (int j = 0; j < col; ++j)
          if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '1') board[i][j] = 'O';
}
    

int main()
{
  vector<vector<char> > board = { { 'X','X', 'X', 'X'},
                                    { 'X','O', 'O', 'X'},
                                    { 'X','X', 'O', 'X'},
                                    { 'X','O', 'X', 'X'}
                                  };
  
  solve_using_dfs(board);

  cout<<"The solution is "<<endl;
  for (int i = 0; i < board.size(); i++)
    {
      for (int j = 0; j < board[0].size(); j++)
      {
        cout<< board[i][j]<<" ";
      }
      cout<<endl;
    }

  return 0;
}