Maksimalūs veidrodžiai, galintys perduoti šviesą iš apačios į dešinę
Pateikta kvadratinė matrica, kurioje kiekvienas langelis reiškia tuščią vietą arba kliūtį. Veidrodžius galime pastatyti tuščioje vietoje. Visi veidrodžiai bus išdėstyti 45 laipsnių kampu, ty jie gali perduoti šviesą iš apačios į dešinę, jei jų kelyje nėra kliūčių.
Šiame klausime turime suskaičiuoti, kiek tokių veidrodžių galima įdėti į kvadratinę matricą, kuri gali perduoti šviesą iš apačios į dešinę.
Pavyzdžiai:
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.
Šią problemą galime išspręsti patikrinę tokių veidrodžių padėtį matricoje, veidrodis, galintis perduoti šviesą iš apačios į dešinę, neturės kliūčių jų kelyje, t.y.
jei veidrodis yra indekse (i j), tada
ties indeksu (k j) nebus kliūčių visiems k i < k <= N
ties indeksu (i k) nebus kliūčių visiems k j < k <= N
Turėdami omenyje aukščiau pateiktas dvi lygtis, galime rasti dešiniausią kliūtį kiekvienoje duotosios matricos iteracijos eilutėje ir žemiausią kliūtį kiekviename stulpelyje kitoje duotosios matricos iteracijoje. Išsaugoję šiuos indeksus atskirame masyve, kiekviename indekse galime patikrinti, ar jis netenkina kliūčių sąlygų, ar ne, tada atitinkamai padidinti skaičių.
Žemiau yra įgyvendintas sprendimas pagal aukščiau pateiktą koncepciją, kuriam reikia O (N^2) laiko ir O (N) papildomos vietos.
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>
Išvestis
2
Laiko sudėtingumas: O(n 2 ).
Pagalbinė erdvė: O(n)
Sukurti viktoriną
