ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

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

prodevelopertutorial November 23, 2018
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:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io