#practiceLinkDiv { display: none !important; }Като се има предвид двоична матрица, която съдържа само 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 = 8Recommended Practice Покритие на всички нули в двоична матрица Опитайте! А просто решение за да разрешим този проблем е чрез преброяване на единици около нули независимо, т.е. изпълняваме цикъл четири пъти във всяка посока за всяка клетка за дадената матрица. Всеки път, когато намерим 1 в който и да е цикъл, ние прекъсваме цикъла и увеличаваме резултата с 1.
Ан ефикасно решение е да направите следното.
- Преминете през всички редове отляво надясно, увеличавайте резултата, ако вече се вижда 1 (при текущото обхождане) и текущият елемент е 0.
- Преминете през всички редове отдясно наляво, увеличавайте резултата, ако вече се вижда 1 (при текущото обхождане) и текущият елемент е 0.
- Преминете през всички колони отгоре надолу, увеличавайте резултата, ако 1 вече се вижда (при текущото обхождане) и текущият елемент е 0.
- Преминете през всички колони отдолу нагоре, увеличавайте резултата, ако вече се вижда 1 (при текущото обхождане) и текущият елемент е 0.
В кода по-долу се взема булева променлива isOne, която се превръща в истина веднага щом се срещне единица в текущото обхождане за всички нули, след като този резултат от итерация се увеличава с една и съща процедура, която се прилага във всичките четири посоки, за да се получи окончателен отговор. Нулираме isOne на false след всяко преминаване.
C++// C++ program to get total coverage of all zeros in // a binary matrix #include
// 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 columns // 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 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. else if (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 else if (isOne): res += 1 # Traversing across columns 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 else if (isOne): res += 1 isOne = False for i in range(R - 1 -1 -1): if (mat[i][j] == 1): isOne = True else if (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# 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[ij] == 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[ij] == 1) isOne = true; else if (isOne) res++; } } // Traversing across columns // 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[ij] == 1) isOne = true; else if (isOne) res++; } isOne = false; for (int i = R-1; i >= 0; i--) { if (mat[ij] == 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.
<script> // Javascript program to get total // coverage of all zeros in // a binary matrix let R = 4; let C = 4; // Returns total coverage // of all zeros in mat[][] function getTotalCoverageOfMatrix(mat) { let res = 0; // looping for all // rows of matrix for (let i = 0; i < R; i++) { // 1 is not seen yet let isOne = false; // looping in columns from // left to right direction // to get left ones for (let 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 (let j = C - 1; j >= 0; j--) { if (mat[i][j] == 1) isOne = true; else if (isOne) res++; } } // Traversing across columns // for up and down directions. for (let j = 0; j < C; j++) { // 1 is not seen yet let isOne = false; for (let i = 0; i < R; i++) { if (mat[i][j] == 1) isOne = true; else if (isOne) res++; } isOne = false; for (let i = R - 1; i >= 0; i--) { if (mat[i][j] == 1) isOne = true; else if (isOne) res++; } } return res; } let mat = [[0 0 0 0] [1 0 0 1] [0 1 1 0] [0 1 0 0]]; document.write(getTotalCoverageOfMatrix(mat)); </script>
Изход
20
Времева сложност: O(n2)
Помощно пространство: O(1)
Създаване на тест