二進制矩陣中所有零的總覆蓋率 · GeeksForGeeks 中文系列教程

# 二進制矩陣中所有零的總覆蓋率 > 原文： [https://www.geeksforgeeks.org/total-coverage-zeros-binary-matrix/](https://www.geeksforgeeks.org/total-coverage-zeros-binary-matrix/) 給定一個僅包含 0 和 1 的二進制矩陣，我們需要找到矩陣所有零的覆蓋率總和，其中特定 0 的覆蓋率定義為左，右，上和左零附近的總數。底部指示。那些可以在任何地方直到某個方向的拐角點。 **示例**： ``` Input : mat[][] = {0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0} Output : 20 First four zeros are surrounded by only one 1\. So coverage for zeros in first row is 1 + 1 + 1 + 1 Zeros in second row are surrounded by three 1's. Note that there is no 1 above. There are 1's in all other three directions. Coverage of zeros in second row = 3 + 3\. Similarly counting for others also, we get overall count as below. 1 + 1 + 1 + 1 + 3 + 3 + 2 + 2 + 2 + 2 + 2 = 20 Input : mat[][] = {1 1 1 0 1 0 0 1} Output : 8 Coverage of first zero is 2 Coverages of other two zeros is 3 Total coverage = 2 + 3 + 3 = 8 ``` 解決此問題的**簡單解決方案**是通過對零周圍的數字進行獨立計數，即對于給定的矩陣，我們在每個方向上針對每個單元在每個方向上運行四次循環。每當在任何循環中找到 1 時，我們都會中斷循環并將結果加 1。一個有效的解決方案**如下。** 1. 從左到右遍歷所有行，如果已經看到 1（在當前遍歷中）并且當前元素為 0，則遞增結果。 2. 從右向左遍歷所有行，如果已經看到 1（在當前遍歷中）并且當前元素為 0，則遞增結果。 3. 從上到下遍歷所有列，如果已經看到 1（在當前遍歷中）并且當前元素為 0，則遞增結果。 4. 從下到上遍歷所有列，如果已經看到 1（在當前遍歷中）并且當前元素為 0，則遞增結果。在下面的代碼中，采用了布爾變量 isOne，當在當前遍歷中遇到一個布爾變量時，該變量即為真，對于迭代之后的所有零，結果加 1，在所有四個方向上應用相同的過程以獲得最終答案。。每次遍歷后，我們將 isOne 重置為 false。 ## C++ ```cpp //? C++ program to get total coverage of all zeros in // a binary matrix #include <bits/stdc++.h> using namespace std; #define R 4 #define C 4 // Returns total coverage of all zeros in mat[][] int getTotalCoverageOfMatrix(int mat[R][C]) { ????int res = 0; ????//? looping for all rows of matrix ????for (int i = 0; i < R; i++) ????{ ????????bool isOne = false;? // 1 is not seen yet ????????// looping in columns from left to right ????????// direction to get left ones ????????for (int j = 0; j < C; j++) ????????{ ????????????// If one is found from left ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????// If 0 is found and we have found ????????????// a 1 before. ????????????else if (isOne) ????????????????res++; ????????} ????????// Repeat the above process for right to ????????// left direction. ????????isOne = false; ????????for (int j = C-1; j >= 0; j--) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????// Traversing across columms for up and down ????// directions. ????for (int j = 0; j < C; j++) ????{ ????????bool isOne = false;? // 1 is not seen yet ????????for (int i = 0; i < R; i++) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????????isOne = false; ????????for (int i = R-1; i >= 0; i--) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????return res; } //? Driver code to test above methods int main() { ????int mat[R][C] = {{0, 0, 0, 0}, ????????{1, 0, 0, 1}, ????????{0, 1, 1, 0}, ????????{0, 1, 0, 0} ????}; ????cout << getTotalCoverageOfMatrix(mat); ????return 0; } ``` ## Java ```java // Java program to get total? // coverage of all zeros in? // a binary matrix import java .io.*; class GFG? { static int R = 4; static int C = 4; // Returns total coverage // of all zeros in mat[][] static int getTotalCoverageOfMatrix(int [][]mat) { ????int res = 0; ????// looping for all? ????// rows of matrix ????for (int i = 0; i < R; i++) ????{ ????????// 1 is not seen yet ????????boolean isOne = false;? ????????// looping in columns from? ????????// left to right direction ????????// to get left ones ????????for (int j = 0; j < C; j++) ????????{ ????????????// If one is found ????????????// from left ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????// If 0 is found and we? ????????????// have found a 1 before. ????????????else if (isOne) ????????????????res++; ????????} ????????// Repeat the above? ????????// process for right? ????????// to left direction. ????????isOne = false; ????????for (int j = C - 1; j >= 0; j--) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????// Traversing across columms ????// for up and down directions. ????for (int j = 0; j < C; j++) ????{ ????????// 1 is not seen yet ????????boolean isOne = false;? ????????for (int i = 0; i < R; i++) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????????isOne = false; ????????for (int i = R - 1; i >= 0; i--) ????????{ ????????????if (mat[i][j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????return res; } // Driver code? static public void main (String[] args) { ????int [][]mat = {{0, 0, 0, 0}, ???????????????????{1, 0, 0, 1}, ???????????????????{0, 1, 1, 0}, ???????????????????{0, 1, 0, 0}}; System.out.println( ???????????getTotalCoverageOfMatrix(mat)); } } // This code is contributed by anuj_67\. ``` ## Python3 ```py # Python3 program to get total coverage of all zeros in # a binary matrix R = 4 C = 4 # Returns total coverage of all zeros in mat[][] def getTotalCoverageOfMatrix(mat): ????res = 0 ????# looping for all rows of matrix ????for i in range(R): ????????isOne = False # 1 is not seen yet ????????# looping in columns from left to right ????????# direction to get left ones ????????for j in range(C): ????????????# If one is found from left ????????????if (mat[i][j] == 1): ????????????????isOne = True ????????????# If 0 is found and we have found ????????????# a 1 before. ????????????elif (isOne): ????????????????res += 1 ????????# Repeat the above process for right to ????????# left direction. ????????isOne = False ????????for j in range(C - 1, -1, -1): ????????????if (mat[i][j] == 1): ????????????????isOne = True ????????????elif (isOne): ????????????????res += 1 ????# Traversing across columms for up and down ????# directions. ????for j in range(C): ????????isOne = False # 1 is not seen yet ????????for i in range(R): ????????????if (mat[i][j] == 1): ????????????????isOne = True ????????????elif (isOne): ????????????????res += 1 ????????isOne = False ????????for i in range(R - 1, -1, -1): ????????????if (mat[i][j] == 1): ????????????????isOne = True ????????????elif (isOne): ????????????????res += 1 ????return res # Driver code mat = [[0, 0, 0, 0],[1, 0, 0, 1],[0, 1, 1, 0],[0, 1, 0, 0]] print(getTotalCoverageOfMatrix(mat)) # This code is contributed by shubhamsingh10 ``` ## C# ```cs // C# program to get total coverage? // of all zeros in a binary matrix using System; class GFG { static int R = 4; static int C = 4; // Returns total coverage of all zeros in mat[][] static int getTotalCoverageOfMatrix(int [,]mat) { ????int res = 0; ????// looping for all rows of matrix ????for (int i = 0; i < R; i++) ????{ ????????// 1 is not seen yet ????????bool isOne = false;? ????????// looping in columns from left to? ????????// right direction to get left ones ????????for (int j = 0; j < C; j++) ????????{ ????????????// If one is found from left ????????????if (mat[i,j] == 1) ????????????????isOne = true; ????????????// If 0 is found and we? ????????????// have found a 1 before. ????????????else if (isOne) ????????????????res++; ????????} ????????// Repeat the above process for? ????????// right to left direction. ????????isOne = false; ????????for (int j = C-1; j >= 0; j--) ????????{ ????????????if (mat[i,j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????// Traversing across columms ????// for up and down directions. ????for (int j = 0; j < C; j++) ????{ ????????// 1 is not seen yet ????????bool isOne = false;? ????????for (int i = 0; i < R; i++) ????????{ ????????????if (mat[i,j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????????isOne = false; ????????for (int i = R-1; i >= 0; i--) ????????{ ????????????if (mat[i,j] == 1) ????????????????isOne = true; ????????????else if (isOne) ????????????????res++; ????????} ????} ????return res; } // Driver code to test above methods ????static public void Main () ????{ ????????int [,]mat = {{0, 0, 0, 0}, ??????????????????????{1, 0, 0, 1}, ??????????????????????{0, 1, 1, 0}, ??????????????????????{0, 1, 0, 0}}; ????Console.WriteLine(getTotalCoverageOfMatrix(mat)); ????} } // This code is contributed by vt_m. ``` **輸出**： ``` 20 ``` **時間復雜度**： `O(n^2)` **輔助空間**：`O(1)` 本文由 [**Utkarsh Trivedi**](https://in.linkedin.com/in/utkarsh-trivedi-253069a7) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。