Er wordt een vierkante matrix gegeven waarin elke cel een blanco of een obstakel vertegenwoordigt. Wij kunnen spiegels op blanco positie plaatsen. Alle spiegels worden onder een hoek van 45 graden geplaatst, dat wil zeggen dat ze licht van onder naar rechts kunnen overbrengen als er geen obstakel op hun pad staat.
Bij deze vraag moeten we tellen hoeveel van dergelijke spiegels er in een vierkante matrix kunnen worden geplaatst die licht van onder naar rechts kunnen overbrengen.
Voorbeelden:
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.
We kunnen dit probleem oplossen door de positie van dergelijke spiegels in de matrix te controleren. De spiegel die licht van onder naar rechts kan overbrengen, zal geen enkel obstakel op hun pad hebben, d.w.z.
als er een spiegel is op index (ij), dan
er zal geen obstakel zijn bij index (k j) voor alle k i< k <= N
er zal geen obstakel zijn bij index (ik) voor alle k j< k <= N
Als we bovenstaande twee vergelijkingen in gedachten houden, kunnen we het meest rechtse obstakel vinden in elke rij in een iteratie van een gegeven matrix en kunnen we het onderste obstakel vinden in elke kolom in een andere iteratie van een gegeven matrix. Nadat we deze indices in een aparte array hebben opgeslagen, kunnen we bij elke index controleren of deze al dan niet aan de voorwaarde voor obstakels voldoet en vervolgens de telling dienovereenkomstig verhogen.
Hieronder is een oplossing geïmplementeerd op basis van het bovenstaande concept, waarvoor O(N^2) tijd en O(N) extra ruimte nodig zijn.
C++// C++ program to find how many mirror can transfer // light from bottom to right #include
// 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 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# 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
<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>
Uitvoer
2
Tijdcomplexiteit: O(n2).
Hulpruimte: O(n)