Tutorialspoint.dev

Count number of islands where every island is row-wise and column-wise separated

Given a rectangular matrix which has only two possible values ‘X’ and ‘O’. The values ‘X’ always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘O’s. Note that islands can only be diagonally adjacent. Count the number of islands in the given matrix.

Examples:

mat[M][N] =  {{'O', 'O', 'O'},
              {'X', 'X', 'O'},
              {'X', 'X', 'O'},
              {'O', 'O', 'X'},
              {'O', 'O', 'X'},
              {'X', 'X', 'O'}
             };
Output: Number of islands is 3

mat[M][N] =  {{'X', 'O', 'O', 'O', 'O', 'O'},
              {'X', 'O', 'X', 'X', 'X', 'X'},
              {'O', 'O', 'O', 'O', 'O', 'O'},
              {'X', 'X', 'X', 'O', 'X', 'X'},
              {'X', 'X', 'X', 'O', 'X', 'X'},
              {'O', 'O', 'O', 'O', 'X', 'X'},
             };
Output: Number of islands is 4

We strongly recommend to minimize your browser and try this yourself first.

The idea is to count all top-leftmost corners of given matrix. We can check if a ‘X’ is top left or not by checking following conditions.
1) A ‘X’ is top of rectangle if the cell just above it is a ‘O’
2) A ‘X’ is leftmost of rectangle if the cell just left of it is a ‘O’

Note that we must check for both conditions as there may be more than one top cells and more than one leftmost cells in a rectangular island. Below is the implementation of above idea.

C/C++



// A C++ program to count the number of rectangular
// islands where every island is separated by a line
#include<iostream>
using namespace std;
  
// Size of given matrix is M X N
#define M 6
#define N 3
  
// This function takes a matrix of 'X' and 'O'
// and returns the number of rectangular islands
// of 'X' where no two islands are row-wise or
// column-wise adjacent, the islands may be diagonaly
// adjacent
int countIslands(int mat[][N])
{
    int count = 0; // Initialize result
  
    // Traverse the input matrix
    for (int i=0; i<M; i++)
    {
        for (int j=0; j<N; j++)
        {
            // If current cell is 'X', then check
            // whether this is top-leftmost of a
            // rectangle. If yes, then increment count
            if (mat[i][j] == 'X')
            {
                if ((i == 0 || mat[i-1][j] == 'O') &&
                    (j == 0 || mat[i][j-1] == 'O'))
                    count++;
            }
        }
    }
  
    return count;
}
  
// Driver program to test above function
int main()
{
    int mat[M][N] =  {{'O', 'O', 'O'},
                      {'X', 'X', 'O'},
                      {'X', 'X', 'O'},
                      {'O', 'O', 'X'},
                      {'O', 'O', 'X'},
                      {'X', 'X', 'O'}
                    };
    cout << "Number of rectangular islands is "
         << countIslands(mat);
    return 0;
}

/div>

Java

// A Java program to count the number of rectangular
// islands where every island is separated by a line
import java.io.*;
  
class islands 
{
    // This function takes a matrix of 'X' and 'O'
    // and returns the number of rectangular islands
    // of 'X' where no two islands are row-wise or
    // column-wise adjacent, the islands may be diagonaly
    // adjacent
    static int countIslands(int mat[][], int m, int n)
    {
        // Initialize result
        int count = 0
  
        // Traverse the input matrix
        for (int i=0; i<m; i++)
        {
            for (int j=0; j<n; j++)
            {
                // If current cell is 'X', then check
                // whether this is top-leftmost of a
                // rectangle. If yes, then increment count
                if (mat[i][j] == 'X')
                {
                    if ((i == 0 || mat[i-1][j] == 'O') &&
                        (j == 0 || mat[i][j-1] == 'O'))
                        count++;
                }
            }
        }
  
        return count;
    }
      
    // Driver program
    public static void main (String[] args) 
    {
        // Size of given matrix is m X n
        int m = 6;
        int n = 3;
        int mat[][] = {{'O', 'O', 'O'},
                        {'X', 'X', 'O'},
                        {'X', 'X', 'O'},
                        {'O', 'O', 'X'},
                        {'O', 'O', 'X'},
                        {'X', 'X', 'O'}
                    };
        System.out.println("Number of rectangular islands is: " 
                                    + countIslands(mat, m, n));
    }
}
  
// This code is contributed by Pramod Kumar

Python3

# A Python3 program to count the number 
# of rectangular islands where every 
# island is separated by a line
  
# Size of given matrix is M X N
M = 6
N = 3
  
# This function takes a matrix of 'X' and 'O'
# and returns the number of rectangular 
# islands of 'X' where no two islands are 
# row-wise or column-wise adjacent, the islands 
# may be diagonaly adjacent
def countIslands(mat):
  
    count = 0; # Initialize result
  
    # Traverse the input matrix
    for i in range (0, M):
      
        for j in range(0, N):
          
            # If current cell is 'X', then check
            # whether this is top-leftmost of a
            # rectangle. If yes, then increment count
            if (mat[i][j] == 'X'):
              
                if ((i == 0 or mat[i - 1][j] == 'O') and
                    (j == 0 or mat[i][j - 1] == 'O')):
                    count = count + 1
              
    return count
  
# Driver Code
mat = [['O', 'O', 'O'],
       ['X', 'X', 'O'],
       ['X', 'X', 'O'],
       ['O', 'O', 'X'],
       ['O', 'O', 'X'],
       ['X', 'X', 'O']]
                  
print("Number of rectangular islands is"
                       countIslands(mat))
  
# This code is contributed by iAyushRaj

C#

// A C# program to count the number of rectangular 
// islands where every island is separated by 
// a line
using System;
  
class GFG {
      
    // This function takes a matrix of 'X' and 'O'
    // and returns the number of rectangular 
    // islands of 'X' where no two islands are
    // row-wise or column-wise adjacent, the
    // islands may be diagonaly adjacent
    static int countIslands(int [,]mat, int m, int n)
    {
          
        // Initialize result
        int count = 0; 
  
        // Traverse the input matrix
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // If current cell is 'X', then check
                // whether this is top-leftmost of a
                // rectangle. If yes, then increment
                // count
                if (mat[i,j] == 'X')
                {
                    if ((i == 0 || mat[i-1,j] == 'O') &&
                        (j == 0 || mat[i,j-1] == 'O'))
                        count++;
                }
            }
        }
  
        return count;
    }
      
    // Driver program
    public static void Main () 
    {
          
        // Size of given matrix is m X n
        int m = 6;
        int n = 3;
        int [,]mat = { {'O', 'O', 'O'},
                       {'X', 'X', 'O'},
                       {'X', 'X', 'O'},
                       {'O', 'O', 'X'},
                       {'O', 'O', 'X'},
                       {'X', 'X', 'O'}
                    };
        Console.WriteLine("Number of rectangular "
         + "islands is: " + countIslands(mat, m, n));
    }
}
  
// This code is contributed by Sam007.

PHP

<?php
// A PHP program to count the
// number of rectangular islands 
// where every island is separated
// by a line
// Size of given matrix is M X N
  
// This function takes a matrix 
// of 'X' and 'O' and returns the
// number of rectangular islands
// of 'X' where no two islands are
// row-wise or column-wise adjacent,
// the islands may be diagonaly
// adjacent
function countIslands($mat)
{
    $M = 6;
    $N = 3;
      
    // Initialize result
    $count = 0; 
  
    // Traverse the input matrix
    for($i = 0; $i < $M; $i++)
    {
        for ($j = 0; $j < $N; $j++)
        {
              
            // If current cell is 
            // 'X', then check whether
            // this is top-leftmost of a
            // rectangle. If yes, then 
            // increment count
            if ($mat[$i][$j] == 'X')
            {
                if (($i == 0 || $mat[$i - 1][$j] == 'O') && 
                    ($j == 0 || $mat[$i][$j-1] == 'O'))
                    $count++;
            }
        }
    }
  
    return $count;
}
  
    // Driver Code
    $mat = array(array('O', 'O', 'O'),
                 array('X', 'X', 'O'),
                 array('X', 'X', 'O'),
                 array('O', 'O', 'X'),
                 array('O', 'O', 'X'),
                 array('X', 'X', 'O'));
    echo "Number of rectangular islands is "
                       , countIslands($mat);
                         
// This code is contributed by nitin mittal
?>

Output:

Number of rectangular islands is 3

Time complexity of this solution is O(MN).



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter