Gesamtabdeckung aller Nullstellen in einer binären Matrix
Probieren Sie es bei GfG Practice aus 
#practiceLinkDiv { display: none !important; }
Ausgabe
#practiceLinkDiv { display: none !important; } Bei einer binären Matrix, die nur Nullen und Einsen enthält, müssen wir die Summe der Abdeckung aller Nullen der Matrix ermitteln, wobei die Abdeckung für eine bestimmte Null als Gesamtzahl der Einsen um eine Null in der Richtung von links nach rechts oben und unten definiert ist. Diese können überall sein, bis die Ecke in eine Richtung zeigt.
Beispiele:
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 Recommended Practice Abdeckung aller Nullen in einer Binärmatrix Probieren Sie es aus! A einfache Lösung Um dieses Problem zu lösen, müssen wir Einsen unabhängig voneinander um Nullen herum zählen, d. h. wir führen für jede Zelle der gegebenen Matrix eine Schleife viermal in jede Richtung aus. Immer wenn wir in einer Schleife eine 1 finden, unterbrechen wir die Schleife und erhöhen das Ergebnis um 1.
Ein effiziente Lösung ist Folgendes zu tun.
- Durchlaufen Sie alle Zeilen von links nach rechts und erhöhen Sie das Ergebnis, wenn bereits eine 1 angezeigt wird (im aktuellen Durchlauf) und das aktuelle Element 0 ist.
- Durchlaufen Sie alle Zeilen von rechts nach links und erhöhen Sie das Ergebnis, wenn bereits eine 1 angezeigt wird (im aktuellen Durchlauf) und das aktuelle Element 0 ist.
- Durchlaufen Sie alle Spalten von oben nach unten und erhöhen Sie das Ergebnis, wenn bereits eine 1 angezeigt wird (im aktuellen Durchlauf) und das aktuelle Element 0 ist.
- Durchlaufen Sie alle Spalten von unten nach oben und erhöhen Sie das Ergebnis, wenn bereits eine 1 angezeigt wird (im aktuellen Durchlauf) und das aktuelle Element 0 ist.
Im folgenden Code wird eine boolesche Variable isOne verwendet, die wahr wird, sobald bei der aktuellen Durchquerung für alle Nullen eine Eins angetroffen wird. Anschließend wird das Iterationsergebnis erhöht, indem dieselbe Prozedur in allen vier Richtungen angewendet wird, um die endgültige Antwort zu erhalten. Wir setzen isOne nach jedem Durchlauf auf false zurück.
C++ // C++ program to get total coverage of all zeros in // a binary matrix #include 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 columns 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 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 # 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# // 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 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 [ 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.
JavaScript < 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>
Ausgabe
20
Zeitkomplexität: O(n 2 )
Hilfsraum: O(1)
Quiz erstellen
