Skip to content
Related Articles

Related Articles

Find perimeter of shapes formed with 1s in binary matrix

View Discussion
Improve Article
Save Article
  • Difficulty Level : Easy
  • Last Updated : 27 Aug, 2022
View Discussion
Improve Article
Save Article

Given a matrix of N rows and M columns, consist of 0’s and 1’s. The task is to find the perimeter of subfigure consisting only 1’s in the matrix. Perimeter of single 1 is 4 as it can be covered from all 4 side. Perimeter of double 11 is 6. 

     
                            
|  1  |           |  1    1  |
                            

Examples:  

Input : mat[][] = 
               {
                 1, 0,
                 1, 1,
               }
Output : 8
Cell (1,0) and (1,1) making a L shape whose perimeter is 8.

Input :  mat[][] = 
                {   
                    0, 1, 0, 0, 0,
                    1, 1, 1, 0, 0,
                    1, 0, 0, 0, 0
                }
Output : 12

perimeter of shapes formed with 1s in binary matrix

The idea is to traverse the matrix, find all ones and find their contribution in perimeter. The maximum contribution of a 1 is four if it is surrounded by all 0s. The contribution reduces by one with 1 around it. 

Algorithm for solving this problem: 

  1. Traverse the whole matrix and find the cell having value equal to 1.
  2. Calculate the number of closed side for that cell and add, 4 – number of closed side to the total perimeter.

Below is the implementation of this approach: 

C++




// C++ program to find perimeter of area covered by
// 1 in 2D matrix consists of 0's and  1's.
#include<bits/stdc++.h>
using namespace std;
#define R 3
#define C 5
 
// Find the number of covered side for mat[i][j].
int numofneighbour(int mat[][C], int i, int j)
{
    int count = 0;
 
    // UP
    if (i > 0 && mat[i - 1][j])
        count++;
 
    // LEFT
    if (j > 0 && mat[i][j - 1])
        count++;
 
    // DOWN
    if (i < R-1 && mat[i + 1][j])
        count++;
 
    // RIGHT
    if (j < C-1 && mat[i][j + 1])
        count++;
 
    return count;
}
 
// Returns sum of perimeter of shapes formed with 1s
int findperimeter(int mat[R][C])
{
    int perimeter = 0;
 
    // Traversing the matrix and finding ones to
    // calculate their contribution.
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (mat[i][j])
                perimeter += (4 - numofneighbour(mat, i ,j));
 
    return perimeter;
}
 
// Driven Program
int main()
{
    int mat[R][C] =
    {
        0, 1, 0, 0, 0,
        1, 1, 1, 0, 0,
        1, 0, 0, 0, 0,
    };
 
    cout << findperimeter(mat) << endl;
 
    return 0;
}

Java




// Java program to find perimeter of area
// covered by 1 in 2D matrix consists
// of 0's and 1's
class GFG {
     
    static final int R = 3;
    static final int C = 5;
     
    // Find the number of covered side
    // for mat[i][j].
    static int numofneighbour(int mat[][],
                            int i, int j)
    {
         
        int count = 0;
     
        // UP
        if (i > 0 && mat[i - 1][j] == 1)
            count++;
     
        // LEFT
        if (j > 0 && mat[i][j - 1] == 1)
            count++;
     
        // DOWN
        if (i < R - 1 && mat[i + 1][j] == 1)
            count++;
     
        // RIGHT
        if (j < C - 1 && mat[i][j + 1] == 1)
            count++;
     
        return count;
    }
     
    // Returns sum of perimeter of shapes
    // formed with 1s
    static int findperimeter(int mat[][])
    {
         
        int perimeter = 0;
     
        // Traversing the matrix and
        // finding ones to calculate
        // their contribution.
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (mat[i][j] == 1)
                    perimeter += (4 -
                    numofneighbour(mat, i, j));
     
        return perimeter;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int mat[][] = {{0, 1, 0, 0, 0},
                       {1, 1, 1, 0, 0},
                       {1, 0, 0, 0, 0}};
                        
        System.out.println(findperimeter(mat));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3




# Python3 program to find perimeter of area
# covered by 1 in 2D matrix consists of 0's and 1's.
 
R = 3
C = 5
 
# Find the number of covered side for mat[i][j].
def numofneighbour(mat, i, j):
 
    count = 0;
 
    # UP
    if (i > 0 and mat[i - 1][j]):
        count+= 1;
 
    # LEFT
    if (j > 0 and mat[i][j - 1]):
        count+= 1;
 
    # DOWN
    if (i < R-1 and mat[i + 1][j]):
        count+= 1
 
    # RIGHT
    if (j < C-1 and mat[i][j + 1]):
        count+= 1;
 
    return count;
 
# Returns sum of perimeter of shapes formed with 1s
def findperimeter(mat):
 
    perimeter = 0;
 
    # Traversing the matrix and finding ones to
    # calculate their contribution.
    for i in range(0, R):
        for j in range(0, C):
            if (mat[i][j]):
                perimeter += (4 - numofneighbour(mat, i, j));
 
    return perimeter;
 
# Driver Code
mat = [ [0, 1, 0, 0, 0],
        [1, 1, 1, 0, 0],
        [1, 0, 0, 0, 0] ]
 
print(findperimeter(mat), end="\n");
 
# This code is contributed by Akanksha Rai

C#




using System;
 
// C# program to find perimeter of area
// covered by 1 in 2D matrix consists 
// of 0's and 1's
public class GFG
{
 
    public  const int R = 3;
    public const int C = 5;
 
    // Find the number of covered side 
    // for mat[i][j].
    public static int numofneighbour(int[][] mat, int i, int j)
    {
 
        int count = 0;
 
        // UP
        if (i > 0 && mat[i - 1][j] == 1)
        {
            count++;
        }
 
        // LEFT
        if (j > 0 && mat[i][j - 1] == 1)
        {
            count++;
        }
 
        // DOWN
        if (i < R - 1 && mat[i + 1][j] == 1)
        {
            count++;
        }
 
        // RIGHT
        if (j < C - 1 && mat[i][j + 1] == 1)
        {
            count++;
        }
 
        return count;
    }
 
    // Returns sum of perimeter of shapes
    // formed with 1s
    public static int findperimeter(int[][] mat)
    {
 
        int perimeter = 0;
 
        // Traversing the matrix and 
        // finding ones to calculate 
        // their contribution.
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                if (mat[i][j] == 1)
                {
                    perimeter += (4 - numofneighbour(mat, i, j));
                }
            }
        }
 
        return perimeter;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[][] mat = new int[][]
        {
            new int[] {0, 1, 0, 0, 0},
            new int[] {1, 1, 1, 0, 0},
            new int[] {1, 0, 0, 0, 0}
        };
 
        Console.WriteLine(findperimeter(mat));
    }
}
 
// This code is contributed by Shrikant13

PHP




<?php
// PHP program to find perimeter of area
// covered by 1 in 2D matrix consists
// of 0's and 1's.
$R = 3;
$C = 5;
 
// Find the number of covered side
// for mat[i][j].
function numofneighbour($mat, $i, $j)
{
    global $R;
    global $C;
    $count = 0;
 
    // UP
    if ($i > 0 && ($mat[$i - 1][$j]))
        $count++;
 
    // LEFT
    if ($j > 0 && ($mat[$i][$j - 1]))
        $count++;
 
    // DOWN
    if (($i < $R-1 )&& ($mat[$i + 1][$j]))
        $count++;
 
    // RIGHT
    if (($j < $C-1) && ($mat[$i][$j + 1]))
        $count++;
 
    return $count;
}
 
// Returns sum of perimeter of shapes
// formed with 1s
function findperimeter($mat)
{
    global $R;
    global $C;
    $perimeter = 0;
 
    // Traversing the matrix and finding ones
    // to calculate their contribution.
    for ($i = 0; $i < $R; $i++)
        for ( $j = 0; $j < $C; $j++)
            if ($mat[$i][$j])
                $perimeter += (4 -
                numofneighbour($mat, $i, $j));
 
    return $perimeter;
}
 
// Driver Code
$mat = array(array(0, 1, 0, 0, 0),
             array(1, 1, 1, 0, 0),
             array(1, 0, 0, 0, 0));
 
echo findperimeter($mat), "\n";
 
// This code is contributed by Sach_Code
?>

Javascript




<script>
 
// JavaScript program to find perimeter of area
// covered by 1 in 2D matrix consists
// of 0's and 1's
let R = 3;
let C = 5;
   
// Find the number of covered side
// for mat[i][j].
function numofneighbour(mat, i, j)
{
    let count = 0;
   
    // UP
    if (i > 0 && mat[i - 1][j] == 1)
        count++;
   
    // LEFT
    if (j > 0 && mat[i][j - 1] == 1)
        count++;
   
    // DOWN
    if (i < R - 1 && mat[i + 1][j] == 1)
        count++;
   
    // RIGHT
    if (j < C - 1 && mat[i][j + 1] == 1)
        count++;
   
    return count;
}
   
// Returns sum of perimeter of shapes
// formed with 1s
function findperimeter(mat)
{
    let perimeter = 0;
   
    // Traversing the matrix and
    // finding ones to calculate
    // their contribution.
    for(let i = 0; i < R; i++)
        for(let j = 0; j < C; j++)
            if (mat[i][j] == 1)
                perimeter += (4 -
                numofneighbour(mat, i, j));
   
    return perimeter;
}
 
// Driver Code
let mat = [ [ 0, 1, 0, 0, 0 ],
            [ 1, 1, 1, 0, 0 ],
            [ 1, 0, 0, 0, 0 ] ];
              
document.write(findperimeter(mat));
 
// This code is contributed by souravghosh0416
 
</script>

Output

12

Time Complexity : O(R x C).
Auxiliary Space: O(1), since no extra space has been taken.

This article is contributed by Aarti_Rathi and Anuj Chauhan(anuj0503). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. 


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!