# 在二進制矩陣中查找以 1s 形成的形狀的周長 > 原文： [https://www.geeksforgeeks.org/find-perimeter-shapes-formed-1s-binary-matrix/](https://www.geeksforgeeks.org/find-perimeter-shapes-formed-1s-binary-matrix/) 給定一個 **N** 行和 **M** 列的矩陣，由 0 和 1 組成。 任務是找到矩陣中僅包含 1 的子圖形的周長。 單 1 的周長是 4，因為它可以從所有 4 側覆蓋。 雙 11 的周長是 6。 ``` | 1 | | 1 1 | ``` 例子： ``` 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 ``` 想法是遍歷矩陣，找到所有矩陣，并找到它們在周長中的作用。 如果 1 被全 0 包圍，則其最大貢獻為 4。 貢獻減少 1 左右。 解決此問題的算法： 1. 遍歷整個矩陣并找到值等于 1 的單元格。 2. 計算該單元格的封閉面數量，然后將 4 –封閉面數量添加到總周長中。 下面是此方法的實現： ## C++ ```cpp // C++ program to find perimeter of area coverede by // 1 in 2D matrix consisits 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 // 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="\n"); # This code is contributed by Akanksha Rai ``` ## C# ```cs 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 ```php <?php // PHP 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].? 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 ``` **時間復雜度**： O（RC）。 本文由 [**Anuj Chauhan（anuj0503）**](https://web.facebook.com/anuj0503) 提供。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。