Posted on by Kalkicode
Code Backtracking

Surrounded Regions

The "Surrounded Regions" problem involves identifying regions in a given matrix where all 'O' elements are surrounded by 'X' elements. The objective is to modify the matrix by replacing those surrounded 'O' elements with 'X'.

Problem Statement

Given a matrix of size R x C, where each element can be either 'X' or 'O', we need to modify the matrix such that all 'O' elements that are surrounded by 'X' are changed to 'X'. An 'O' element is considered surrounded if it is not on the boundary of the matrix and all its adjacent elements (top, bottom, left, and right) are 'X'.

For example, consider the following matrix:

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

After modifying the matrix, the result should be:

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

The surrounded 'O' elements in the matrix have been replaced with 'X', while the elements on the boundaries remain unchanged.

Explanation

The problem can be solved by performing a depth-first search (DFS) or breadth-first search (BFS) traversal of the matrix.

First, we iterate through the matrix and replace all 'O' elements with a different symbol, such as '+', to mark them for later processing. This is done to avoid modifying 'O' elements that are not surrounded by 'X'.

Next, we traverse the boundary of the matrix and perform a DFS or BFS from each 'O' element found on the boundary. During the traversal, we recursively visit adjacent elements and change them to 'O'. This ensures that all elements connected to the boundary 'O' elements are marked as not surrounded by 'X'.

After the traversal is complete, all remaining '+' elements are the ones that were originally surrounded by 'X'. We replace them with 'X' to achieve the desired result.

Pseudocode Algorithm

function fill(record, i, j):
    if i < 0 or i >= R or j < 0 or j >= C:
        return

    if record[i][j] == '+':
        record[i][j] = 'O'

        fill(record, i + 1, j)
        fill(record, i - 1, j)
        fill(record, i, j + 1)
        fill(record, i, j - 1)

function solve(record):
    for i from 0 to R:
        for j from 0 to C:
            if record[i][j] == 'O':
                record[i][j] = '+'

    for i from 0 to R:
        if record[i][0] == '+':
            fill(record, i, 0)

        if record[i][C-1] == '+':
            fill(record, i, C-1)

    for i from 0 to C:
        if record[0][i] == '+':
            fill(record, 0, i)

        if record[R-1][i] == '+':
            fill(record, R-1, i)

    for i from 0 to R:
        for j from 0 to C:
            if record[i][j] == '+':
                record[i][j] = 'X'

record = [
    ['O', 'X', 'X', 'X', 'X', 'O', 'X'],
    ['X', 'X', 'X', 'X', 'O', 'X', 'O'],
    ['O', 'O', 'O', 'X', 'X', 'O', 'O'],
    ['X', 'O', 'X', 'X', 'X', 'X', 'X'],
    ['X', 'X', 'O', 'X', 'X', 'X', 'X'],
    ['X', 'O', 'X', 'X', 'X', 'X', 'X'],
    ['X', 'X', 'O', 'O', 'X', 'O', 'O'],
    ['X', 'X', 'O', 'X', 'O', 'X', 'O'],
]

solve(record)

Code Solution

/*
   C Program for
   Surrounded Regions
*/
#include <stdio.h>
#define R 8 
#define C 7

// Print record elements
void printResult(char record[R][C])
{
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            
            printf(" %c",record[i][j]);
            
        }
        printf("\n");
    }  
}
// Fill corner elements with a "O" value
void fill(char record[R][C],int i, int j)
{
   if(i < 0 || i >= R || j < 0 || j >= C)
   {
        return;
   }

   if(record[i][j] == '+')
   {
        // Update element
        record[i][j] = 'O';

        // visit to down element
        fill(record,i+1,j);
        // visit to up element
        fill(record,i-1,j);

        // visit to right element
        fill(record,i,j+1);
        // visit to left element
        fill(record,i,j-1);   
   }
}

// Fill surrounded regions
void solve(char record[R][C])
{
    // loop controlling variables
    int i = 0;
    int j = 0;
    printf("\n Before Surrounded \n");
    printResult(record);
    // First change the all zero with other symbol  "+"
    for ( i = 0; i < R; ++i)
    {
        for ( j = 0; j < C; ++j)
        {
            if(record[i][j]=='O')
            {
                record[i][j] = '+';
            }
        }
    } 
    // Change boundary 
    // Check first and last column
    for ( i = 0; i < R; ++i)
    {
        if(record[i][0] == '+')
        {
            fill(record,i,0);
        }

        if(record[i][C-1]=='+')
        {
            fill(record,i,C-1);
        }
    }

    // Check first and last row
    for ( i = 0; i < C; ++i)
    {
        if(record[0][i] == '+')
        {
            fill(record,0,i);
        }

        if(record[R-1][i]=='+')
        {
            fill(record,R-1,i);
        }
    }
    for ( i = 0; i < R; ++i)
    {
        for ( j = 0; j < C; ++j)
        {
            if(record[i][j]=='+')
            {
                record[i][j] = 'X';
            }
        }
    } 
    printf("\n After Surrounded \n");
    printResult(record);
}

int main()
{
    char record[R][C] =  
    {
        {'O', 'X', 'X', 'X', 'X', 'O', 'X'},
        {'X', 'X', 'X', 'X', 'O', 'X', 'O'},
        {'O', 'O', 'O', 'X', 'X', 'O', 'O'},
        {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'O', 'X', 'O', 'O'},
        {'X', 'X', 'O', 'X', 'O', 'X', 'O'},
    };
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,Right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X

            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    solve(record);

    return 0;
}

Output

 Before Surrounded
 O X X X X O X
 X X X X O X O
 O O O X X O O
 X O X X X X X
 X X O X X X X
 X O X X X X X
 X X O O X O O
 X X O X O X O

 After Surrounded
 O X X X X O X
 X X X X X X O
 O O O X X O O
 X O X X X X X
 X X X X X X X
 X X X X X X X
 X X O O X O O
 X X O X O X O
/*
   Java Program for
   surrounded regions
*/
public class Regions
{
    // Print record elements
    public void printresult(char[][] record, int r, int c)
    {
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                System.out.print("  " + record[i][j]);
            }
            System.out.print("\n");
        }
    }
    // Fill corner elements with a "O" value
    public void fill(char[][] record, int i, int j, int r, int c)
    {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record[i][j] == '+')
        {
            // Update element
            record[i][j] = 'O';
            // visit to down element
            fill(record, i + 1, j, r, c);
            // visit to up element
            fill(record, i - 1, j, r, c);
            // visit to right element
            fill(record, i, j + 1, r, c);
            // visit to left element
            fill(record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    public void solve(char[][] record)
    {
        // loop controlling variables
        int i = 0;
        int j = 0;
        int r = record.length;
        int c = record[0].length;
        System.out.print("\n Before Surrounded \n");
        printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i][j] == 'O')
                {
                    record[i][j] = '+';
                }
            }
        }
        // change boundary 
        // check first and last column
        for (i = 0; i < r; ++i)
        {
            if (record[i][0] == '+')
            {
                fill(record, i, 0, r, c);
            }
            if (record[i][c - 1] == '+')
            {
                fill(record, i, c - 1, r, c);
            }
        }
        // check first and last row
        for (i = 0; i < c; ++i)
        {
            if (record[0][i] == '+')
            {
                fill(record, 0, i, r, c);
            }
            if (record[r - 1][i] == '+')
            {
                fill(record, r - 1, i, r, c);
            }
        }
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i][j] == '+')
                {
                    record[i][j] = 'X';
                }
            }
        }
        System.out.print("\n After Surrounded \n");
        printresult(record, r, c);
    }
    public static void main(String[] args)
    {
        Regions task = new Regions();
        char [][]record =  
        {
            {'O', 'X', 'X', 'X', 'X', 'O', 'X'},
            {'X', 'X', 'X', 'X', 'O', 'X', 'O'},
            {'O', 'O', 'O', 'X', 'X', 'O', 'O'},
            {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
            {'X', 'X', 'O', 'X', 'X', 'X', 'X'},
            {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
            {'X', 'X', 'O', 'O', 'X', 'O', 'O'},
            {'X', 'X', 'O', 'X', 'O', 'X', 'O'},
        };
        /*
            Change all O with X when O is Surrounded by X
            Example
            ========
            // Left,right, Bottom and Top are have X
                X   X
            X   O   O  X
                X   X
            
            Then change center O with X

                X   X
            X   X   X  X
                X   X
            -----------------------------
            or
                X
            X   O  X
                X   
            Then change center O with X
                X
            X   O  X
                X    
        */
        task.solve(record);
    }
}

Output

 Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

 After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
// Include header file
#include <iostream>
#define R 8 
#define C 7
using namespace std;
/*
   C++ Program for
   surrounded regions
*/
class Regions
{
    public:
        // Print record elements
        void printresult(char record[R][C])
        {
            for (int i = 0; i < R; ++i)
            {
                for (int j = 0; j < C; ++j)
                {
                    cout << "  " << record[i][j];
                }
                cout << "\n";
            }
        }
    // Fill corner elements with a "O" value
    void fill(char record[R][C], int i, int j)
    {
        if (i < 0 || i >= R || j < 0 || j >= C)
        {
            return;
        }
        if (record[i][j] == '+')
        {
            // Update element
            record[i][j] = 'O';
            // visit to down element
            this->fill(record, i + 1, j);
            // visit to up element
            this->fill(record, i - 1, j);
            // visit to right element
            this->fill(record, i, j + 1);
            // visit to left element
            this->fill(record, i, j - 1);
        }
    }
    // Fill surrounded regions
    void solve(char record[R][C])
    {
        // loop controlling variables
        int i = 0;
        int j = 0;
  
        cout << "\n  Before Surrounded \n";
        this->printresult(record);
        // First change the all zero with other symbol  "+"
        for (i = 0; i < R; ++i)
        {
            for (j = 0; j < C; ++j)
            {
                if (record[i][j] == 'O')
                {
                    record[i][j] = '+';
                }
            }
        }
        // change boundary
        // check first and last column
        for (i = 0; i < R; ++i)
        {
            if (record[i][0] == '+')
            {
                this->fill(record, i, 0);
            }
            if (record[i][C - 1] == '+')
            {
                this->fill(record, i, C - 1);
            }
        }
        // check first and last row
        for (i = 0; i < C; ++i)
        {
            if (record[0][i] == '+')
            {
                this->fill(record, 0, i);
            }
            if (record[R - 1][i] == '+')
            {
                this->fill(record, R - 1, i);
            }
        }
        for (i = 0; i < R; ++i)
        {
            for (j = 0; j < C; ++j)
            {
                if (record[i][j] == '+')
                {
                    record[i][j] = 'X';
                }
            }
        }
        cout << "\n  After Surrounded \n";
        this->printresult(record);
    }
};
int main()
{
    Regions task = Regions();
    char record[R][C] =  
    {
        {'O', 'X', 'X', 'X', 'X', 'O', 'X'},
        {'X', 'X', 'X', 'X', 'O', 'X', 'O'},
        {'O', 'O', 'O', 'X', 'X', 'O', 'O'},
        {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'O', 'X', 'O', 'O'},
        {'X', 'X', 'O', 'X', 'O', 'X', 'O'},
    };
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X
            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    task.solve(record);
    return 0;
}

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
// Include namespace system
using System;
/*
   C# Program for
   surrounded regions
*/
public class Regions
{
    // Print record elements
    public void printresult(char[,] record, int r, int c)
    {
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                Console.Write("  " + record[i,j]);
            }
            Console.Write("\n");
        }
    }
    // Fill corner elements with a "O" value
    public void fill(char[,] record, int i, int j, int r, int c)
    {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record[i,j] == '+')
        {
            // Update element
            record[i,j] = 'O';
            // visit to down element
            fill(record, i + 1, j, r, c);
            // visit to up element
            fill(record, i - 1, j, r, c);
            // visit to right element
            fill(record, i, j + 1, r, c);
            // visit to left element
            fill(record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    public void solve(char[,] record)
    {
        // loop controlling variables
        int i = 0;
        int j = 0;
        int r = record.GetLength(0);
        int c = record.GetLength(1);
        Console.Write("\n  Before Surrounded \n");
        printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i,j] == 'O')
                {
                    record[i,j] = '+';
                }
            }
        }
        // change boundary
        // check first and last column
        for (i = 0; i < r; ++i)
        {
            if (record[i,0] == '+')
            {
                fill(record, i, 0, r, c);
            }
            if (record[i,c - 1] == '+')
            {
                fill(record, i, c - 1, r, c);
            }
        }
        // check first and last row
        for (i = 0; i < c; ++i)
        {
            if (record[0,i] == '+')
            {
                fill(record, 0, i, r, c);
            }
            if (record[r - 1,i] == '+')
            {
                fill(record, r - 1, i, r, c);
            }
        }
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i,j] == '+')
                {
                    record[i,j] = 'X';
                }
            }
        }
        Console.Write("\n  After Surrounded \n");
        printresult(record, r, c);
    }
    public static void Main(String[] args)
    {
        Regions task = new Regions();
        char[,] record = 
        {
            {'O', 'X', 'X', 'X', 'X', 'O', 'X'},
            {'X', 'X', 'X', 'X', 'O', 'X', 'O'},
            {'O', 'O', 'O', 'X', 'X', 'O', 'O'},
            {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
            {'X', 'X', 'O', 'X', 'X', 'X', 'X'},
            {'X', 'O', 'X', 'X', 'X', 'X', 'X'},
            {'X', 'X', 'O', 'O', 'X', 'O', 'O'},
            {'X', 'X', 'O', 'X', 'O', 'X', 'O'}
        };
        /*
            Change all O with X when O is Surrounded by X
            Example
            ========
            // Left,right, Bottom and Top are have X
                X   X
            X   O   O  X
                X   X
            
            Then change center O with X
                X   X
            X   X   X  X
                X   X
            -----------------------------
            or
                X
            X   O  X
                X   
            Then change center O with X
                X
            X   O  X
                X    
        */
        task.solve(record);
    }
}

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
<?php
/*
   Php Program for
   surrounded regions
*/
class Regions
{
    // Print record elements
    public  function printresult( & $record, $r, $c)
    {
        for ($i = 0; $i < $r; ++$i)
        {
            for ($j = 0; $j < $c; ++$j)
            {
                echo "  ". $record[$i][$j];
            }
            echo "\n";
        }
    }
    // Fill corner elements with a "O" value
    public  function fill( & $record, $i, $j, $r, $c)
    {
        if ($i < 0 || $i >= $r || $j < 0 || $j >= $c)
        {
            return;
        }
        if ($record[$i][$j] == '+')
        {
            // Update element
            $record[$i][$j] = 'O';
            // visit to down element
            $this->fill($record, $i + 1, $j, $r, $c);
            // visit to up element
            $this->fill($record, $i - 1, $j, $r, $c);
            // visit to right element
            $this->fill($record, $i, $j + 1, $r, $c);
            // visit to left element
            $this->fill($record, $i, $j - 1, $r, $c);
        }
    }
    // Fill surrounded regions
    public  function solve( & $record)
    {
        // loop controlling variables
        $i = 0;
        $j = 0;
        $r = count($record);
        $c = count($record[0]);
        echo "\n  Before Surrounded \n";
        $this->printresult($record, $r, $c);
        // First change the all zero with other symbol  "+"
        for ($i = 0; $i < $r; ++$i)
        {
            for ($j = 0; $j < $c; ++$j)
            {
                if ($record[$i][$j] == 'O')
                {
                    $record[$i][$j] = '+';
                }
            }
        }
        // change boundary
        // check first and last column
        for ($i = 0; $i < $r; ++$i)
        {
            if ($record[$i][0] == '+')
            {
                $this->fill($record, $i, 0, $r, $c);
            }
            if ($record[$i][$c - 1] == '+')
            {
                $this->fill($record, $i, $c - 1, $r, $c);
            }
        }
        // check first and last row
        for ($i = 0; $i < $c; ++$i)
        {
            if ($record[0][$i] == '+')
            {
                $this->fill($record, 0, $i, $r, $c);
            }
            if ($record[$r - 1][$i] == '+')
            {
                $this->fill($record, $r - 1, $i, $r, $c);
            }
        }
        for ($i = 0; $i < $r; ++$i)
        {
            for ($j = 0; $j < $c; ++$j)
            {
                if ($record[$i][$j] == '+')
                {
                    $record[$i][$j] = 'X';
                }
            }
        }
        echo "\n  After Surrounded \n";
        $this->printresult($record, $r, $c);
    }
}

function main()
{
    $task = new Regions();
    $record = array(
      array('O', 'X', 'X', 'X', 'X', 'O', 'X'), 
      array('X', 'X', 'X', 'X', 'O', 'X', 'O'), 
      array('O', 'O', 'O', 'X', 'X', 'O', 'O'), 
      array('X', 'O', 'X', 'X', 'X', 'X', 'X'), 
      array('X', 'X', 'O', 'X', 'X', 'X', 'X'), 
      array('X', 'O', 'X', 'X', 'X', 'X', 'X'), 
      array('X', 'X', 'O', 'O', 'X', 'O', 'O'), 
      array('X', 'X', 'O', 'X', 'O', 'X', 'O')
    );
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X
            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    $task->solve($record);
}
main();

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
/*
   Node Js Program for
   surrounded regions
*/
class Regions
{
    // Print record elements
    printresult(record, r, c)
    {
        for (var i = 0; i < r; ++i)
        {
            for (var j = 0; j < c; ++j)
            {
                process.stdout.write("  " + record[i][j]);
            }
            process.stdout.write("\n");
        }
    }
    // Fill corner elements with a "O" value
    fill(record, i, j, r, c)
    {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record[i][j] == '+')
        {
            // Update element
            record[i][j] = 'O';
            // visit to down element
            this.fill(record, i + 1, j, r, c);
            // visit to up element
            this.fill(record, i - 1, j, r, c);
            // visit to right element
            this.fill(record, i, j + 1, r, c);
            // visit to left element
            this.fill(record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    solve(record)
    {
        // loop controlling variables
        var i = 0;
        var j = 0;
        var r = record.length;
        var c = record[0].length;
        process.stdout.write("\n  Before Surrounded \n");
        this.printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i][j] == 'O')
                {
                    record[i][j] = '+';
                }
            }
        }
        // change boundary
        // check first and last column
        for (i = 0; i < r; ++i)
        {
            if (record[i][0] == '+')
            {
                this.fill(record, i, 0, r, c);
            }
            if (record[i][c - 1] == '+')
            {
                this.fill(record, i, c - 1, r, c);
            }
        }
        // check first and last row
        for (i = 0; i < c; ++i)
        {
            if (record[0][i] == '+')
            {
                this.fill(record, 0, i, r, c);
            }
            if (record[r - 1][i] == '+')
            {
                this.fill(record, r - 1, i, r, c);
            }
        }
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (record[i][j] == '+')
                {
                    record[i][j] = 'X';
                }
            }
        }
        process.stdout.write("\n  After Surrounded \n");
        this.printresult(record, r, c);
    }
}

function main()
{
    var task = new Regions();
    var record = [
      ['O', 'X', 'X', 'X', 'X', 'O', 'X'] , 
      ['X', 'X', 'X', 'X', 'O', 'X', 'O'] , 
      ['O', 'O', 'O', 'X', 'X', 'O', 'O'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'X', 'X', 'X', 'X'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'O', 'X', 'O', 'O'] , 
      ['X', 'X', 'O', 'X', 'O', 'X', 'O']
    ];
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X
            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    task.solve(record);
}
main();

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
#    Python 3 Program for
#    surrounded regions

class Regions :
    #  Print record elements
    def printresult(self, record, r, c) :
        i = 0
        j = 0
        while (i < r) :
            while (j < c) :
                print("  ", record[i][j], end = "")
                j += 1
            
            print(end = "\n")
            i += 1
            j = 0
        
    
    #  Fill corner elements with a "O" value
    def fill(self, record, i, j, r, c) :
        if (i < 0 or i >= r or j < 0 or j >= c) :
            return
        
        if (record[i][j] == '+') :
            #  Update element
            record[i][j] = 'O'
            #  visit to down element
            self.fill(record, i + 1, j, r, c)
            #  visit to up element
            self.fill(record, i - 1, j, r, c)
            #  visit to right element
            self.fill(record, i, j + 1, r, c)
            #  visit to left element
            self.fill(record, i, j - 1, r, c)
        
    
    #  Fill surrounded regions
    def solve(self, record) :
        #  loop controlling variables
        i = 0
        j = 0
        r = len(record)
        c = len(record[0])
        print("\n  Before Surrounded ")
        self.printresult(record, r, c)
        #  First change the all zero with other symbol  "+"
        while (i < r) :
            while (j < c) :
                if (record[i][j] == 'O') :
                    record[i][j] = '+'
                
                j += 1
            
            i += 1
            j = 0
        
        #  change boundary
        #  check first and last column
        i = 0
        while (i < r) :
            if (record[i][0] == '+') :
                self.fill(record, i, 0, r, c)
            
            if (record[i][c - 1] == '+') :
                self.fill(record, i, c - 1, r, c)
            
            i += 1
        
        #  check first and last row
        i = 0
        while (i < c) :
            if (record[0][i] == '+') :
                self.fill(record, 0, i, r, c)
            
            if (record[r - 1][i] == '+') :
                self.fill(record, r - 1, i, r, c)
            
            i += 1
        
        i = 0
        while (i < r) :
            j = 0
            while (j < c) :
                if (record[i][j] == '+') :
                    record[i][j] = 'X'
                
                j += 1
            
            i += 1
        
        print("\n  After Surrounded ")
        self.printresult(record, r, c)
    

def main() :
    task = Regions()
    record = [
      ['O', 'X', 'X', 'X', 'X', 'O', 'X'] , 
      ['X', 'X', 'X', 'X', 'O', 'X', 'O'] , 
      ['O', 'O', 'O', 'X', 'X', 'O', 'O'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'X', 'X', 'X', 'X'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'O', 'X', 'O', 'O'] , 
      ['X', 'X', 'O', 'X', 'O', 'X', 'O']
    ]
    # 
    #     Change all O with X when O is Surrounded by X
    #     Example
    #     ========
    #     // Left,right, Bottom and Top are have X
    #         X   X
    #     X   O   O  X
    #         X   X
    #     
    #     Then change center O with X
    #         X   X
    #     X   X   X  X
    #         X   X
    #     -----------------------------
    #     or
    #         X
    #     X   O  X
    #         X   
    #     Then change center O with X
    #         X
    #     X   O  X
    #         X    
    
    task.solve(record)

if __name__ == "__main__": main()

Output

  Before Surrounded
   O   X   X   X   X   O   X
   X   X   X   X   O   X   O
   O   O   O   X   X   O   O
   X   O   X   X   X   X   X
   X   X   O   X   X   X   X
   X   O   X   X   X   X   X
   X   X   O   O   X   O   O
   X   X   O   X   O   X   O

  After Surrounded
   O   X   X   X   X   O   X
   X   X   X   X   X   X   O
   O   O   O   X   X   O   O
   X   O   X   X   X   X   X
   X   X   X   X   X   X   X
   X   X   X   X   X   X   X
   X   X   O   O   X   O   O
   X   X   O   X   O   X   O
#    Ruby Program for
#    surrounded regions

class Regions 
    #  Print record elements
    def printresult(record, r, c) 
        i = 0
        j = 0
        while (i < r) 
            while (j < c) 
                print("  ", record[i][j])
                j += 1
            end

            print("\n")
            i += 1
            j = 0
        end

    end

    #  Fill corner elements with a "O" value
    def fill(record, i, j, r, c) 
        if (i < 0 || i >= r || j < 0 || j >= c) 
            return
        end

        if (record[i][j] == '+') 
            #  Update element
            record[i][j] = 'O'
            #  visit to down element
            self.fill(record, i + 1, j, r, c)
            #  visit to up element
            self.fill(record, i - 1, j, r, c)
            #  visit to right element
            self.fill(record, i, j + 1, r, c)
            #  visit to left element
            self.fill(record, i, j - 1, r, c)
        end

    end

    #  Fill surrounded regions
    def solve(record) 
        #  loop controlling variables
        i = 0
        j = 0
        r = record.length
        c = record[0].length
        print("\n  Before Surrounded \n")
        self.printresult(record, r, c)
        #  First change the all zero with other symbol  "+"
        while (i < r) 
            while (j < c) 
                if (record[i][j] == 'O') 
                    record[i][j] = '+'
                end

                j += 1
            end

            i += 1
            j = 0
        end

        #  change boundary
        #  check first and last column
        i = 0
        while (i < r) 
            if (record[i][0] == '+') 
                self.fill(record, i, 0, r, c)
            end

            if (record[i][c - 1] == '+') 
                self.fill(record, i, c - 1, r, c)
            end

            i += 1
        end

        #  check first and last row
        i = 0
        while (i < c) 
            if (record[0][i] == '+') 
                self.fill(record, 0, i, r, c)
            end

            if (record[r - 1][i] == '+') 
                self.fill(record, r - 1, i, r, c)
            end

            i += 1
        end

        i = 0
        while (i < r) 
            j = 0
            while (j < c) 
                if (record[i][j] == '+') 
                    record[i][j] = 'X'
                end

                j += 1
            end

            i += 1
        end

        print("\n  After Surrounded \n")
        self.printresult(record, r, c)
    end

end

def main() 
    task = Regions.new()
    record = [
      ['O', 'X', 'X', 'X', 'X', 'O', 'X'] , 
      ['X', 'X', 'X', 'X', 'O', 'X', 'O'] , 
      ['O', 'O', 'O', 'X', 'X', 'O', 'O'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'X', 'X', 'X', 'X'] , 
      ['X', 'O', 'X', 'X', 'X', 'X', 'X'] , 
      ['X', 'X', 'O', 'O', 'X', 'O', 'O'] , 
      ['X', 'X', 'O', 'X', 'O', 'X', 'O']
    ]
    # 
    #     Change all O with X when O is Surrounded by X
    #     Example
    #     ========
    #     // Left,right, Bottom and Top are have X
    #         X   X
    #     X   O   O  X
    #         X   X
    #     
    #     Then change center O with X
    #         X   X
    #     X   X   X  X
    #         X   X
    #     -----------------------------
    #     or
    #         X
    #     X   O  X
    #         X   
    #     Then change center O with X
    #         X
    #     X   O  X
    #         X    
    
    task.solve(record)
end

main()

Output

  Before Surrounded 
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded 
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
/*
   Scala Program for
   surrounded regions
*/
class Regions
{
    // Print record elements
    def printresult(record: Array[Array[Character]], r: Int, c: Int): Unit = {
        var i: Int = 0;
        var j: Int = 0;
        while (i < r)
        {
            while (j < c)
            {
                print("  " + record(i)(j));
                j += 1;
            }
            print("\n");
            i += 1;
            j = 0;
        }
    }
    // Fill corner elements with a "O" value
    def fill(record: Array[Array[Character]], i: Int, j: Int, r: Int, c: Int): Unit = {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record(i)(j) == '+')
        {
            // Update element
            record(i)(j) = 'O';
            // visit to down element
            this.fill(record, i + 1, j, r, c);
            // visit to up element
            this.fill(record, i - 1, j, r, c);
            // visit to right element
            this.fill(record, i, j + 1, r, c);
            // visit to left element
            this.fill(record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    def solve(record: Array[Array[Character]]): Unit = {
        // loop controlling variables
        var i: Int = 0;
        var j: Int = 0;
        var r: Int = record.length;
        var c: Int = record(0).length;
        print("\n  Before Surrounded \n");
        this.printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        while (i < r)
        {
            while (j < c)
            {
                if (record(i)(j) == 'O')
                {
                    record(i)(j) = '+';
                }
                j += 1;
            }
            i += 1;
            j = 0;
        }
        // change boundary
        // check first and last column
        i = 0;
        while (i < r)
        {
            if (record(i)(0) == '+')
            {
                this.fill(record, i, 0, r, c);
            }
            if (record(i)(c - 1) == '+')
            {
                this.fill(record, i, c - 1, r, c);
            }
            i += 1;
        }
        // check first and last row
        i = 0;
        while (i < c)
        {
            if (record(0)(i) == '+')
            {
                this.fill(record, 0, i, r, c);
            }
            if (record(r - 1)(i) == '+')
            {
                this.fill(record, r - 1, i, r, c);
            }
            i += 1;
        }
        i = 0;
        while (i < r)
        {
            j = 0;
            while (j < c)
            {
                if (record(i)(j) == '+')
                {
                    record(i)(j) = 'X';
                }
                j += 1;
            }
            i += 1;
        }
        print("\n  After Surrounded \n");
        this.printresult(record, r, c);
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Regions = new Regions();
        var record: Array[Array[Character]] = Array(
          Array('O', 'X', 'X', 'X', 'X', 'O', 'X'), 
          Array('X', 'X', 'X', 'X', 'O', 'X', 'O'), 
          Array('O', 'O', 'O', 'X', 'X', 'O', 'O'), 
          Array('X', 'O', 'X', 'X', 'X', 'X', 'X'), 
          Array('X', 'X', 'O', 'X', 'X', 'X', 'X'), 
          Array('X', 'O', 'X', 'x', 'X', 'X', 'X'), 
          Array('X', 'X', 'O', 'O', 'X', 'O', 'O'), 
          Array('X', 'X', 'O', 'X', 'O', 'X', 'O')
        );
        /*
            Change all O with X when O is Surrounded by X
            Example
            ========
            // Left,right, Bottom and Top are have X
                X   X
            X   O   O  X
                X   X
            
            Then change center O with X
                X   X
            X   X   X  X
                X   X
            -----------------------------
            or
                X
            X   O  X
                X   
            Then change center O with X
                X
            X   O  X
                X    
        */
        task.solve(record);
    }
}

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O
/*
   Swift 4 Program for
   surrounded regions
*/
class Regions
{
    // Print record elements
    func printresult(_ record: [
        [Character]
    ], _ r: Int, _ c: Int)
    {
        var i: Int = 0;
        var j: Int = 0;
        while (i < r)
        {
            while (j < c)
            {
                print("  ", record[i][j], terminator: "");
                j += 1;
            }
            print(terminator: "\n");
            i += 1;
            j = 0;
        }
    }
    // Fill corner elements with a "O" value
    func fill(_ record: inout[[Character]], _ i: Int, _ j: Int, _ r: Int, _ c: Int)
    {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record[i][j] == "+")
        {
            // Update element
            record[i][j] = "O";
            // visit to down element
            self.fill(&record, i + 1, j, r, c);
            // visit to up element
            self.fill(&record, i - 1, j, r, c);
            // visit to right element
            self.fill(&record, i, j + 1, r, c);
            // visit to left element
            self.fill(&record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    func solve(_ record: inout[[Character]])
    {
        // loop controlling variables
        var i: Int = 0;
        var j: Int = 0;
        let r: Int = record.count;
        let c: Int = record[0].count;
        print("\n  Before Surrounded ");
        self.printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        while (i < r)
        {
            while (j < c)
            {
                if (record[i][j] == "O")
                {
                    record[i][j] = "+";
                }
                j += 1;
            }
            i += 1;
            j = 0;
        }
        // change boundary
        // check first and last column
        i = 0;
        while (i < r)
        {
            if (record[i][0] == "+")
            {
                self.fill(&record, i, 0, r, c);
            }
            if (record[i][c - 1] == "+")
            {
                self.fill(&record, i, c - 1, r, c);
            }
            i += 1;
        }
        // check first and last row
        i = 0;
        while (i < c)
        {
            if (record[0][i] == "+")
            {
                self.fill(&record, 0, i, r, c);
            }
            if (record[r - 1][i] == "+")
            {
                self.fill(&record, r - 1, i, r, c);
            }
            i += 1;
        }
        i = 0;
        while (i < r)
        {
            j = 0;
            while (j < c)
            {
                if (record[i][j] == "+")
                {
                    record[i][j] = "X";
                }
                j += 1;
            }
            i += 1;
        }
        print("\n  After Surrounded ");
        self.printresult(record, r, c);
    }
}
func main()
{
    let task: Regions = Regions();
    var record: [[Character]] = [
      ["O", "X", "X", "X", "X", "O", "X"] , 
      ["X", "X", "X", "X", "O", "X", "O"] , 
      ["O", "O", "O", "X", "X", "O", "O"] , 
      ["X", "O", "X", "X", "X", "X", "X"] , 
      ["X", "X", "O", "X", "X", "X", "X"] , 
      ["X", "O", "X", "X", "X", "X", "X"] , 
      ["X", "X", "O", "O", "X", "O", "O"] , 
      ["X", "X", "O", "X", "O", "X", "O"]
    ];
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X
            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    task.solve(&record);
}
main();

Output

  Before Surrounded
   O   X   X   X   X   O   X
   X   X   X   X   O   X   O
   O   O   O   X   X   O   O
   X   O   X   X   X   X   X
   X   X   O   X   X   X   X
   X   O   X   X   X   X   X
   X   X   O   O   X   O   O
   X   X   O   X   O   X   O

  After Surrounded
   O   X   X   X   X   O   X
   X   X   X   X   X   X   O
   O   O   O   X   X   O   O
   X   O   X   X   X   X   X
   X   X   X   X   X   X   X
   X   X   X   X   X   X   X
   X   X   O   O   X   O   O
   X   X   O   X   O   X   O
/*
   Kotlin Program for
   surrounded regions
*/
class Regions
{
    // Print record elements
    fun printresult(record: Array <Array<Char>> , r: Int, c: Int): Unit
    {
        var i: Int = 0;
        var j: Int = 0;
        while (i < r)
        {
            while (j < c)
            {
                print("  " + record[i][j]);
                j += 1;
            }
            print("\n");
            i += 1;
            j = 0;
        }
    }
    // Fill corner elements with a "O" value
    fun fill(record: Array <Array<Char>> , i: Int, j: Int, r: Int, c: Int): Unit
    {
        if (i < 0 || i >= r || j < 0 || j >= c)
        {
            return;
        }
        if (record[i][j] == '+')
        {
            // Update element
            record[i][j] = 'O';
            // visit to down element
            this.fill(record, i + 1, j, r, c);
            // visit to up element
            this.fill(record, i - 1, j, r, c);
            // visit to right element
            this.fill(record, i, j + 1, r, c);
            // visit to left element
            this.fill(record, i, j - 1, r, c);
        }
    }
    // Fill surrounded regions
    fun solve(record: Array < Array < Char >> ): Unit
    {
        // loop controlling variables
        var i: Int = 0;
        var j: Int = 0;
        var r: Int = record.count();
        var c: Int = record[0].count();
        print("\n  Before Surrounded \n");
        this.printresult(record, r, c);
        // First change the all zero with other symbol  "+"
        while (i < r)
        {
            while (j < c)
            {
                if (record[i][j] == 'O')
                {
                    record[i][j] = '+';
                }
                j += 1;
            }
            i += 1;
            j = 0;
        }
        // change boundary
        // check first and last column
        i = 0;
        while (i < r)
        {
            if (record[i][0] == '+')
            {
                this.fill(record, i, 0, r, c);
            }
            if (record[i][c - 1] == '+')
            {
                this.fill(record, i, c - 1, r, c);
            }
            i += 1;
        }
        // check first and last row
        i = 0;
        while (i < c)
        {
            if (record[0][i] == '+')
            {
                this.fill(record, 0, i, r, c);
            }
            if (record[r - 1][i] == '+')
            {
                this.fill(record, r - 1, i, r, c);
            }
            i += 1;
        }
        i = 0;
        while (i < r)
        {
            j = 0;
            while (j < c)
            {
                if (record[i][j] == '+')
                {
                    record[i][j] = 'X';
                }
                j += 1;
            }
            i += 1;
        }
        print("\n  After Surrounded \n");
        this.printresult(record, r, c);
    }
}
fun main(args: Array <String> ): Unit
{
    var task: Regions = Regions();
    var record: Array<Array<Char>> = arrayOf(
      arrayOf('O', 'X', 'X', 'X', 'X', 'O', 'X'), 
      arrayOf('X', 'X', 'X', 'X', 'O', 'X', 'O'), 
      arrayOf('O', 'O', 'O', 'X', 'X', 'O', 'O'), 
      arrayOf('X', 'O', 'X', 'X', 'X', 'X', 'X'), 
      arrayOf('X', 'X', 'O', 'X', 'X', 'X', 'X'), 
      arrayOf('X', 'O', 'X', 'X', 'X', 'X', 'X'), 
      arrayOf('X', 'X', 'O', 'O', 'X', 'O', 'O'), 
      arrayOf('X', 'X', 'O', 'X', 'O', 'X', 'O')
    );
    /*
        Change all O with X when O is Surrounded by X
        Example
        ========
        // Left,right, Bottom and Top are have X
            X   X
        X   O   O  X
            X   X
        
        Then change center O with X
            X   X
        X   X   X  X
            X   X
        -----------------------------
        or
            X
        X   O  X
            X   
        Then change center O with X
            X
        X   O  X
            X    
    */
    task.solve(record);
}

Output

  Before Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  O  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  O  X  X  X  X
  X  O  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

  After Surrounded
  O  X  X  X  X  O  X
  X  X  X  X  X  X  O
  O  O  O  X  X  O  O
  X  O  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  X  X  X  X  X
  X  X  O  O  X  O  O
  X  X  O  X  O  X  O

Time Complexity

The time complexity of the solution is O(R * C) because we perform a traversal of the entire matrix to replace 'O' with '+', and then traverse the boundary elements to perform the DFS or BFS operation. The space complexity is O(1) as we modify the input matrix in place without using any additional data structures.

Output Explanation

Before surrounded, the matrix is:

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

After surrounded, the matrix is:

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

The 'O' elements that were surrounded by 'X' have been replaced with 'X', while the boundary elements and other 'O' elements that were not surrounded remain unchanged.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment