# Find perimeter of shapes formed with 1s in binary matrix

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 ```

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 coverede by ` `// 1 in 2D matrix consisits of 0's and  1's. ` `#include ` `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 ` `// coverede by 1 in 2D matrix consisits  ` `// 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. `

## Python 3

 `# Python 3 program to find perimeter of area  ` `# covered by 1 in 2D matrix consisits 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``=````" "````); ` ` `  `# This code is contributed by Akanksha Rai `

## C#

 `using` `System; ` ` `  `// C# program to find perimeter of area  ` `// coverede by 1 in 2D matrix consisits   ` `// 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

 ` 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``), ````" "````;  ` ` `  `// This code is contributed by Sach_Code ` `?> `

Output:

```12
```

Time Complexity : O(RC).

## tags:

Geometric Matrix Matrix Geometric