Given a 2D board with X and O, get all the region surrounded by X, explanation in CPP

Input:

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

Output:

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

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

Solution in C++

#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;
}

Output:

The solution is
X X X X
X X X X
X X X X
X O X X

List Of Tutorials available in this website: