Maximale Spiegel, die Licht von unten nach rechts übertragen können
Es wird eine quadratische Matrix angegeben, in der jede Zelle entweder eine Lücke oder ein Hindernis darstellt. Wir können Spiegel an leeren Positionen platzieren. Alle Spiegel sind im 45-Grad-Winkel angeordnet, d. h. sie können das Licht von unten nach rechts übertragen, wenn ihnen kein Hindernis im Weg steht.
Bei dieser Frage müssen wir zählen, wie viele solcher Spiegel in einer quadratischen Matrix platziert werden können, die Licht von unten nach rechts übertragen können.
Beispiele:
Output for above example is 2. In above diagram mirror at (3 1) and (5 5) are able to send light from bottom to right so total possible mirror count is 2.
Wir können dieses Problem lösen, indem wir die Position solcher Spiegel in der Matrix überprüfen. Der Spiegel, der Licht von unten nach rechts übertragen kann, wird kein Hindernis auf seinem Weg haben, d. h.
Wenn am Index (i j) ein Spiegel vorhanden ist, dann
Für alle k i wird es am Index (k j) kein Hindernis geben < k <= N
Für alle k j wird es am Index (i k) kein Hindernis geben < k <= N
Unter Berücksichtigung der beiden oben genannten Gleichungen können wir in einer Iteration einer gegebenen Matrix in jeder Zeile das Hindernis ganz rechts finden und in einer anderen Iteration einer gegebenen Matrix in jeder Spalte das unterste Hindernis. Nachdem wir diese Indizes in einem separaten Array gespeichert haben, können wir bei jedem Index prüfen, ob er die Bedingung „Kein Hindernis“ erfüllt oder nicht, und dann die Anzahl entsprechend erhöhen.
Nachfolgend finden Sie eine implementierte Lösung für das obige Konzept, die O(N^2) Zeit und O(N) zusätzlichen Speicherplatz erfordert.
C++ // C++ program to find how many mirror can transfer // light from bottom to right #include using namespace std ; // method returns number of mirror which can transfer // light from bottom to right int maximumMirrorInMatrix ( string mat [] int N ) { // To store first obstacles horizontally (from right) // and vertically (from bottom) int horizontal [ N ] vertical [ N ]; // initialize both array as -1 signifying no obstacle memset ( horizontal -1 sizeof ( horizontal )); memset ( vertical -1 sizeof ( vertical )); // looping matrix to mark column for obstacles for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N -1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] == 'B' ) continue ; // mark rightmost column with obstacle horizontal [ i ] = j ; break ; } } // looping matrix to mark rows for obstacles for ( int j = 0 ; j < N ; j ++ ) { for ( int i = N -1 ; i >= 0 ; i -- ) { if ( mat [ i ][ j ] == 'B' ) continue ; // mark leftmost row with obstacle vertical [ j ] = i ; break ; } } int res = 0 ; // Initialize result // if there is not obstacle on right or below // then mirror can be placed to transfer light for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { /* if i > vertical[j] then light can from bottom if j > horizontal[i] then light can go to right */ if ( i > vertical [ j ] && j > horizontal [ i ]) { /* uncomment this code to print actual mirror position also cout < < i < < ' ' < < j < < endl; */ res ++ ; } } } return res ; } // Driver code to test above method int main () { int N = 5 ; // B - Blank O - Obstacle string mat [ N ] = { 'BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' }; cout < < maximumMirrorInMatrix ( mat N ) < < endl ; return 0 ; }
Java // Java program to find how many mirror can transfer // light from bottom to right import java.util.* ; class GFG { // method returns number of mirror which can transfer // light from bottom to right static int maximumMirrorInMatrix ( String mat [] int N ) { // To store first obstacles horizontally (from right) // and vertically (from bottom) int [] horizontal = new int [ N ] ; int [] vertical = new int [ N ] ; // initialize both array as -1 signifying no obstacle Arrays . fill ( horizontal - 1 ); Arrays . fill ( vertical - 1 ); // looping matrix to mark column for obstacles for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N - 1 ; j >= 0 ; j -- ) { if ( mat [ i ] . charAt ( j ) == 'B' ) { continue ; } // mark rightmost column with obstacle horizontal [ i ] = j ; break ; } } // looping matrix to mark rows for obstacles for ( int j = 0 ; j < N ; j ++ ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( mat [ i ] . charAt ( j ) == 'B' ) { continue ; } // mark leftmost row with obstacle vertical [ j ] = i ; break ; } } int res = 0 ; // Initialize result // if there is not obstacle on right or below // then mirror can be placed to transfer light for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { /* if i > vertical[j] then light can from bottom if j > horizontal[i] then light can go to right */ if ( i > vertical [ j ] && j > horizontal [ i ] ) { /* uncomment this code to print actual mirror position also cout < < i < < ' ' < < j < < endl; */ res ++ ; } } } return res ; } // Driver code public static void main ( String [] args ) { int N = 5 ; // B - Blank O - Obstacle String mat [] = { 'BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' }; System . out . println ( maximumMirrorInMatrix ( mat N )); } } /* This code is contributed by PrinciRaj1992 */
Python3 # Python3 program to find how many mirror can transfer # light from bottom to right # method returns number of mirror which can transfer # light from bottom to right def maximumMirrorInMatrix ( mat N ): # To store first obstacles horizontally (from right) # and vertically (from bottom) horizontal = [ - 1 for i in range ( N )] vertical = [ - 1 for i in range ( N )]; # looping matrix to mark column for obstacles for i in range ( N ): for j in range ( N - 1 - 1 - 1 ): if ( mat [ i ][ j ] == 'B' ): continue ; # mark rightmost column with obstacle horizontal [ i ] = j ; break ; # looping matrix to mark rows for obstacles for j in range ( N ): for i in range ( N - 1 - 1 - 1 ): if ( mat [ i ][ j ] == 'B' ): continue ; # mark leftmost row with obstacle vertical [ j ] = i ; break ; res = 0 ; # Initialize result # if there is not obstacle on right or below # then mirror can be placed to transfer light for i in range ( N ): for j in range ( N ): ''' if i > vertical[j] then light can from bottom if j > horizontal[i] then light can go to right ''' if ( i > vertical [ j ] and j > horizontal [ i ]): ''' uncomment this code to print actual mirror position also''' res += 1 ; return res ; # Driver code to test above method N = 5 ; # B - Blank O - Obstacle mat = [ 'BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' ]; print ( maximumMirrorInMatrix ( mat N )); # This code is contributed by rutvik_56.
C# // C# program to find how many mirror can transfer // light from bottom to right using System ; class GFG { // method returns number of mirror which can transfer // light from bottom to right static int maximumMirrorInMatrix ( String [] mat int N ) { // To store first obstacles horizontally (from right) // and vertically (from bottom) int [] horizontal = new int [ N ]; int [] vertical = new int [ N ]; // initialize both array as -1 signifying no obstacle for ( int i = 0 ; i < N ; i ++ ) { horizontal [ i ] =- 1 ; vertical [ i ] =- 1 ; } // looping matrix to mark column for obstacles for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N - 1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] == 'B' ) { continue ; } // mark rightmost column with obstacle horizontal [ i ] = j ; break ; } } // looping matrix to mark rows for obstacles for ( int j = 0 ; j < N ; j ++ ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( mat [ i ][ j ] == 'B' ) { continue ; } // mark leftmost row with obstacle vertical [ j ] = i ; break ; } } int res = 0 ; // Initialize result // if there is not obstacle on right or below // then mirror can be placed to transfer light for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { /* if i > vertical[j] then light can from bottom if j > horizontal[i] then light can go to right */ if ( i > vertical [ j ] && j > horizontal [ i ]) { /* uncomment this code to print actual mirror position also cout < < i < < ' ' < < j < < endl; */ res ++ ; } } } return res ; } // Driver code public static void Main ( String [] args ) { int N = 5 ; // B - Blank O - Obstacle String [] mat = { 'BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' }; Console . WriteLine ( maximumMirrorInMatrix ( mat N )); } } // This code is contributed by Princi Singh
JavaScript < script > // JavaScript program to find how many mirror can transfer // light from bottom to right // method returns number of mirror which can transfer // light from bottom to right function maximumMirrorInMatrix ( mat N ) { // To store first obstacles horizontally (from right) // and vertically (from bottom) var horizontal = Array ( N ). fill ( - 1 ); var vertical = Array ( N ). fill ( - 1 ); // looping matrix to mark column for obstacles for ( var i = 0 ; i < N ; i ++ ) { for ( var j = N - 1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] == 'B' ) { continue ; } // mark rightmost column with obstacle horizontal [ i ] = j ; break ; } } // looping matrix to mark rows for obstacles for ( var j = 0 ; j < N ; j ++ ) { for ( var i = N - 1 ; i >= 0 ; i -- ) { if ( mat [ i ][ j ] == 'B' ) { continue ; } // mark leftmost row with obstacle vertical [ j ] = i ; break ; } } var res = 0 ; // Initialize result // if there is not obstacle on right or below // then mirror can be placed to transfer light for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < N ; j ++ ) { /* if i > vertical[j] then light can from bottom if j > horizontal[i] then light can go to right */ if ( i > vertical [ j ] && j > horizontal [ i ]) { /* uncomment this code to print actual mirror position also cout < < i < < ' ' < < j < < endl; */ res ++ ; } } } return res ; } // Driver code var N = 5 ; // B - Blank O - Obstacle var mat = [ 'BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' ]; document . write ( maximumMirrorInMatrix ( mat N )); < /script>
Ausgabe
2
Zeitkomplexität: O(n 2 ).
Hilfsraum: O(n)
Quiz erstellen
