Tutorialspoint.dev

Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’

Given a matrix where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

Examples:

Input: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };
Output: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'X', 'X', 'X'},
                      {'O', 'X', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'O', 'X', 'O'},
                      {'O', 'O', 'X', 'O', 'O', 'O'},
                    };


Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'O', 'O', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };
Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };



This is mainly an application of Flood-Fill algorithm. The main difference here is that a ‘O’ is not replaced by ‘X’ if it lies in region that ends on a boundary. Following are simple steps to do this special flood fill.

1) Traverse the given matrix and replace all ‘O’ with a special character ‘-‘.

2) Traverse four edges of given matrix and call floodFill(‘-‘, ‘O’) for every ‘-‘ on edges. The remaining ‘-‘ are the characters that indicate ‘O’s (in the original matrix) to be replaced by ‘X’.

3) Traverse the matrix and replace all ‘-‘s with ‘X’s.

Let us see steps of above algorithm with an example. Let following be the input matrix. 

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Step 1: Replace all ‘O’ with ‘-‘. 

       mat[M][N] =  {{'X', '-', 'X', 'X', 'X', 'X'},
                     {'X', '-', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'-', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', '-', 'X', '-'},
                     {'-', '-', 'X', '-', '-', '-'},
                    };

Step 2: Call floodFill(‘-‘, ‘O’) for all edge elements with value equals to ‘-‘ 

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Step 3: Replace all ‘-‘ with ‘X’. 

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

The following is implementation of above algorithm.

C++

// A C++ program to replace all 'O's with 'X''s if surrounded by 'X'
#include<iostream>
using namespace std;
  
// Size of given matrix is M X N
#define M 6
#define N 6
  
  
// A recursive function to replace previous value 'prevV' at  '(x, y)'
// and all surrounding values of (x, y) with new value 'newV'.
void floodFillUtil(char mat[][N], int x, int y, char prevV, char newV)
{
    // Base cases
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;
    if (mat[x][y] != prevV)
        return;
  
    // Replace the color at (x, y)
    mat[x][y] = newV;
  
    // Recur for north, east, south and west
    floodFillUtil(mat, x+1, y, prevV, newV);
    floodFillUtil(mat, x-1, y, prevV, newV);
    floodFillUtil(mat, x, y+1, prevV, newV);
    floodFillUtil(mat, x, y-1, prevV, newV);
}
  
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int replaceSurrounded(char mat[][N])
{
   // Step 1: Replace all 'O'  with '-'
   for (int i=0; i<M; i++)
      for (int j=0; j<N; j++)
          if (mat[i][j] == 'O')
             mat[i][j] = '-';
  
   // Call floodFill for all '-' lying on edges
   for (int i=0; i<M; i++)   // Left side
      if (mat[i][0] == '-')
        floodFillUtil(mat, i, 0, '-', 'O');
   for (int i=0; i<M; i++)  //  Right side
      if (mat[i][N-1] == '-')
        floodFillUtil(mat, i, N-1, '-', 'O');
   for (int i=0; i<N; i++)   // Top side
      if (mat[0][i] == '-')
        floodFillUtil(mat, 0, i, '-', 'O');
   for (int i=0; i<N; i++)  // Bottom side
      if (mat[M-1][i] == '-')
        floodFillUtil(mat, M-1, i, '-', 'O');
  
   // Step 3: Replace all '-' with 'X'
   for (int i=0; i<M; i++)
      for (int j=0; j<N; j++)
         if (mat[i][j] == '-')
             mat[i][j] = 'X';
  
}
  
// Driver program to test above function
int main()
{
    char mat[][N] =  {{'X', 'O', 'X', 'O', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };
    replaceSurrounded(mat);
  
  
    for (int i=0; i<M; i++)
    {
      for (int j=0; j<N; j++)
          cout << mat[i][j] << " ";
      cout << endl;
    }
    return 0;
}

Java

// A Java program to replace 
// all 'O's with 'X''s if 
// surrounded by 'X'
import java.io.*;
  
class GFG
{
    static int M = 6;
    static int N = 6;
    static void floodFillUtil(char mat[][], int x, 
                              int y, char prevV, 
                              char newV)
    {
        // Base cases
        if (x < 0 || x >= M ||
            y < 0 || y >= N)
            return;
              
        if (mat[x][y] != prevV)
            return;
      
        // Replace the color at (x, y)
        mat[x][y] = newV;
      
        // Recur for north,
        // east, south and west
        floodFillUtil(mat, x + 1, y, 
                      prevV, newV);
        floodFillUtil(mat, x - 1, y, 
                      prevV, newV);
        floodFillUtil(mat, x, y + 1, 
                      prevV, newV);
        floodFillUtil(mat, x, y - 1, 
                      prevV, newV);
    }
      
    // Returns size of maximum 
    // size subsquare matrix
    // surrounded by 'X'
    static void replaceSurrounded(char mat[][])
    {
          
    // Step 1: Replace 
    // all 'O' with '-'
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (mat[i][j] == 'O')
                mat[i][j] = '-';
      
    // Call floodFill for 
    // all '-' lying on edges
    for (int i = 0; i < M; i++) // Left side
        if (mat[i][0] == '-')
            floodFillUtil(mat, i, 0, 
                          '-', 'O');
    for (int i = 0; i < M; i++) // Right side
        if (mat[i][N - 1] == '-')
            floodFillUtil(mat, i, N - 1,
                          '-', 'O');
    for (int i = 0; i < N; i++) // Top side
        if (mat[0][i] == '-')
            floodFillUtil(mat, 0, i,
                          '-', 'O');
    for (int i = 0; i < N; i++) // Bottom side
        if (mat[M - 1][i] == '-')
            floodFillUtil(mat, M - 1, 
                          i, '-', 'O');
      
    // Step 3: Replace 
    // all '-' with 'X'
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (mat[i][j] == '-')
                mat[i][j] = 'X';
    }
      
    // Driver Code
    public static void main (String[] args)
    {
        char[][] mat = {{'X', 'O', 'X', 
                         'O', 'X', 'X'},
                        {'X', 'O', 'X', 
                         'X', 'O', 'X'},
                        {'X', 'X', 'X', 
                         'O', 'X', 'X'},
                        {'O', 'X', 'X',
                         'X', 'X', 'X'},
                        {'X', 'X', 'X',
                         'O', 'X', 'O'},
                        {'O', 'O', 'X',
                         'O', 'O', 'O'}};
                          
        replaceSurrounded(mat);
      
        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(mat[i][j] + " "); 
                  
            System.out.println("");
        }
    }
}
  
// This code is contributed 
// by shiv_bhakt

C#

// A C# program to replace 
// all 'O's with 'X''s if 
// surrounded by 'X'
using System;
  
class GFG
{
    static int M = 6;
    static int N = 6;
    static void floodFillUtil(char [,]mat, int x, 
                              int y, char prevV, 
                              char newV)
    {
        // Base cases
        if (x < 0 || x >= M ||
            y < 0 || y >= N)
            return;
              
        if (mat[x, y] != prevV)
            return;
      
        // Replace the color at (x, y)
        mat[x, y] = newV;
       
        // Recur for north,
        // east, south and west
        floodFillUtil(mat, x + 1, y, 
                       prevV, newV);
        floodFillUtil(mat, x - 1, y, 
                       prevV, newV);
        floodFillUtil(mat, x, y + 1, 
                       prevV, newV);
        floodFillUtil(mat, x, y - 1, 
                       prevV, newV);
    }
      
    // Returns size of maximum 
    // size subsquare matrix
    // surrounded by 'X'
    static void replaceSurrounded(char [,]mat)
    {
          
    // Step 1: Replace 
    // all 'O' with '-'
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (mat[i, j] == 'O')
                mat[i, j] = '-';
      
    // Call floodFill for 
    // all '-' lying on edges
    for (int i = 0; i < M; i++) // Left side
        if (mat[i, 0] == '-')
            floodFillUtil(mat, i, 0, 
                          '-', 'O');
    for (int i = 0; i < M; i++) // Right side
        if (mat[i, N - 1] == '-')
            floodFillUtil(mat, i, N - 1,
                          '-', 'O');
    for (int i = 0; i < N; i++) // Top side
        if (mat[0, i] == '-')
            floodFillUtil(mat, 0, i,
                          '-', 'O');
    for (int i = 0; i < N; i++) // Bottom side
        if (mat[M - 1, i] == '-')
            floodFillUtil(mat, M - 1, 
                          i, '-', 'O');
      
    // Step 3: Replace 
    // all '-' with 'X'
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (mat[i, j] == '-')
                mat[i, j] = 'X';
    }
      
    // Driver Code
    public static void Main ()
    {
        char [,]mat = new char[,]
                        {{'X', 'O', 'X', 
                          'O', 'X', 'X'},
                         {'X', 'O', 'X', 
                          'X', 'O', 'X'},
                         {'X', 'X', 'X', 
                          'O', 'X', 'X'},
                         {'O', 'X', 'X',
                          'X', 'X', 'X'},
                         {'X', 'X', 'X',
                          'O', 'X', 'O'},
                         {'O', 'O', 'X',
                          'O', 'O', 'O'}};
                          
        replaceSurrounded(mat);
      
        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
                Console.Write(mat[i, j] + " "); 
                  
            Console.WriteLine("");
        }
    }
}
  
// This code is contributed 
// by shiv_bhakt

PHP

<?php 
// A PHP program to replace all 
// 'O's with 'X''s if surrounded by 'X'
  
// Size of given 
// matrix is M X N
$M = 6;
$N = 6;
  
  
// A recursive function to replace 
// previous value 'prevV' at '(x, y)'
// and all surrounding values of 
// (x, y) with new value 'newV'.
function floodFillUtil(&$mat, $x, $y, 
                        $prevV, $newV)
{
    // Base cases
    if ($x < 0 || $x >= $GLOBALS['M'] || 
        $y < 0 || $y >= $GLOBALS['N'])
        return;
    if ($mat[$x][$y] != $prevV)
        return;
  
    // Replace the color at (x, y)
    $mat[$x][$y] = $newV;
  
    // Recur for north,
    // east, south and west
    floodFillUtil($mat, $x + 1, $y, $prevV, $newV);
    floodFillUtil($mat, $x - 1, $y, $prevV, $newV);
    floodFillUtil($mat, $x, $y + 1, $prevV, $newV);
    floodFillUtil($mat, $x, $y - 1, $prevV, $newV);
}
  
// Returns size of maximum 
// size subsquare matrix
// surrounded by 'X'
function replaceSurrounded(&$mat)
{
      
// Step 1: Replace all 'O' with '-'
for ($i = 0; $i < $GLOBALS['M']; $i++)
    for ($j = 0; $j < $GLOBALS['N']; $j++)
        if ($mat[$i][$j] == 'O')
            $mat[$i][$j] = '-';
  
// Call floodFill for all
// '-' lying on edges
for ($i = 0; 
     $i < $GLOBALS['M']; $i++) // Left side
    if ($mat[$i][0] == '-')
        floodFillUtil($mat, $i, 0, '-', 'O');
          
for ($i = 0; $i < $GLOBALS['M']; $i++) // Right side
    if ($mat[$i][$GLOBALS['N'] - 1] == '-')
        floodFillUtil($mat, $i,
                      $GLOBALS['N'] - 1, '-', 'O');
          
for ($i = 0; $i < $GLOBALS['N']; $i++) // Top side
    if ($mat[0][$i] == '-')
        floodFillUtil($mat, 0, $i, '-', 'O');
          
for ($i = 0; $i < $GLOBALS['N']; $i++) // Bottom side
    if ($mat[$GLOBALS['M'] - 1][$i] == '-')
        floodFillUtil($mat, $GLOBALS['M'] - 1, 
                            $i, '-', 'O');
  
// Step 3: Replace all '-' with 'X'
for ($i = 0; $i < $GLOBALS['M']; $i++)
    for ($j = 0; $j < $GLOBALS['N']; $j++)
        if ($mat[$i][$j] == '-')
            $mat[$i][$j] = 'X';
  
}
  
// Driver Code
$mat = array(array('X', 'O', 'X', 'O', 'X', 'X'),
             array('X', 'O', 'X', 'X', 'O', 'X'),
             array('X', 'X', 'X', 'O', 'X', 'X'),
             array('O', 'X', 'X', 'X', 'X', 'X'),
             array('X', 'X', 'X', 'O', 'X', 'O'),
             array('O', 'O', 'X', 'O', 'O', 'O'));
replaceSurrounded($mat);
  
for ($i = 0; $i < $GLOBALS['M']; $i++)
{
    for ($j = 0; $j < $GLOBALS['N']; $j++)
        echo $mat[$i][$j]." ";
    echo " ";
}
  
// This code is contributed by ChitraNayal
?>


Output: 

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

Time Complexity of the above solution is O(MN). Note that every element of matrix is processed at most three times.



This article is attributed to GeeksforGeeks.org

tags:

Graph Matrix Recursion Google Google Recursion Matrix Graph
Prev Next
More topics on Matrix Archives

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Matrix Archives Print a given matrix in spiral...
Matrix Archives Row wise sorting in 2D array
Matrix Archives Find difference between sums o...
Matrix Archives Print matrix in zag-zag fashio...
Matrix Archives Boundary elements of a Matrix
Matrix Archives Check given matrix is magic sq...