Find perimeter of shapes formed with 1s in binary matrix
Given a matrix of N rows and M columns, consisting of 0‘s and 1‘s. The task is to find the perimeter of the subfigure consisting of only 1s in the matrix. The perimeter of a figure is given by the total number of horizontal and vertical linings formed by the boundary 1s of the subfigure. Each line is considered to have a length of 1 unit.
Note: There exists only one subfigure consisting of 1s
Examples:
Input : mat[][] = {{1,0},{1,1}}
Output : 8
Explanation:Input : mat[][] = {{0, 1, 0, 0, 0},{1, 1, 1, 0, 0},{1, 0, 0, 0, 0}}
Output : 12
Explanation:
Approach:
The idea is to traverse the matrix, find all ones and find their contribution in perimeter as per the below cases:
Case 1 (4 adjacent 1s) : contribution = 0
Case 2 (3 adjacent 1s) : contribution = 1
Case 3 (2 adjacent 1s) : contribution = 2
Case 4 (1 adjacent 1s) : contribution = 3
Case 5 (0 adjacent 1s) : contribution = 4Finally return the sum of contribution of each 1 in the matrix as the answer.
- Traverse the whole matrix and find the cell having value equal to 1.
- Calculate the number of adjacent 1s for that cell and add, 4 – number of adjacent 1s 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 import java.io.*; 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 |
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> |
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 ?> |
12
Time Complexity: O(R x C).
Auxiliary Space: O(1), since no extra space has been taken.
If you like w3wiki and would like to contribute, you can also write an article using write.w3wiki.net or mail your article to review-team@w3wiki.net. See your article appearing on the w3wiki main page and help other Beginner.
Contact Us