Maksimalna zrcala koja mogu prenositi svjetlost odozdo desno
Dana je kvadratna matrica u kojoj svaka ćelija predstavlja ili prazninu ili prepreku. Ogledala možemo postaviti na prazno mjesto. Sva zrcala bit će smještena pod kutom od 45 stupnjeva, tj. mogu prenositi svjetlost odozdo udesno ako nema prepreka na njihovom putu.
U ovom pitanju trebamo izbrojati koliko se takvih zrcala može smjestiti u kvadratnu matricu koja može prenositi svjetlost odozdo desno.
Primjeri:
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.
Ovaj problem možemo riješiti provjerom položaja takvih zrcala u matrici zrcalo koje može prenijeti svjetlost odozdo na desno neće imati nikakve prepreke na svom putu, tj.
ako je zrcalo tamo na indeksu (i j) tada
neće biti prepreka na indeksu (k j) za sve k i < k <= N
neće biti prepreka kod indeksa (i k) za sve k j < k <= N
Imajući na umu gornje dvije jednadžbe, možemo pronaći krajnju desnu prepreku u svakom retku u jednoj iteraciji dane matrice i možemo pronaći najnižu prepreku u svakom stupcu u drugoj iteraciji dane matrice. Nakon pohranjivanja ovih indeksa u zasebnom nizu možemo provjeriti za svaki indeks zadovoljava li uvjet bez prepreka ili ne i zatim povećati broj u skladu s tim.
U nastavku je implementirano rješenje za gornji koncept koji zahtijeva O(N^2) vremena i O(N) dodatnog prostora.
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>
Izlaz
2
Vremenska složenost: O(n 2 ).
Pomoćni prostor: O(n)
Napravi kviz
