Maksimal spejle som kan overføre lys fra bund til højre
Der er givet en kvadratisk matrix, hvor hver celle repræsenterer enten et blanktegn eller en forhindring. Vi kan placere spejle i tom position. Alle spejle vil være placeret ved 45 grader, det vil sige, at de kan overføre lys fra bund til højre, hvis der ikke er nogen hindring i deres vej.
I dette spørgsmål skal vi tælle, hvor mange sådanne spejle der kan placeres i kvadratisk matrix, som kan overføre lys fra bund til højre.
Eksempler:
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.
Vi kan løse dette problem ved at kontrollere placeringen af sådanne spejle i matrix, spejlet, som kan overføre lys fra bund til højre, vil ikke have nogen hindring i deres vej, dvs.
hvis et spejl er der ved indeks (i j) så
der vil ikke være nogen hindring ved indeks (k j) for alle k i < k <= N
der vil ikke være nogen hindring ved indeks (ik) for alle k j < k <= N
Ved at holde ovenstående to ligninger i tankerne, kan vi finde den yderste højre hindring ved hver række i en iteration af given matrix, og vi kan finde den nederste forhindring ved hver kolonne i en anden iteration af given matrix. Efter at have lagret disse indekser i et separat array kan vi ved hvert indeks kontrollere, om det ikke opfylder nogen forhindringsbetingelser eller ej, og derefter øge antallet i overensstemmelse hermed.
Nedenfor er implementeret løsning på ovenstående koncept, som kræver O(N^2) tid og O(N) ekstra plads.
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>
Produktion
2
Tidskompleksitet: O(n 2 ).
Hjælpeplads: O(n)
Opret quiz
