Viene fornita una matrice quadrata in cui ciascuna cella rappresenta uno spazio vuoto o un ostacolo. Possiamo posizionare gli specchi in una posizione vuota. Tutti gli specchi saranno posizionati a 45 gradi, ovvero potranno trasferire la luce dal basso a destra se non vi sono ostacoli sul loro percorso.
In questa domanda dobbiamo contare quanti di questi specchi possono essere posizionati in una matrice quadrata che può trasferire la luce dal basso a destra.
Esempi:
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.
Possiamo risolvere questo problema controllando la posizione di tali specchi nella matrice, lo specchio che può trasferire la luce dal basso a destra non avrà alcun ostacolo sul suo percorso, ad es.
se c'è uno specchio nell'indice (ij), allora
non ci sarà alcun ostacolo all'indice (k j) per ogni k i< k <= N
non ci sarà alcun ostacolo all'indice (i k) per ogni k j< k <= N
Tenendo presente le due equazioni precedenti, possiamo trovare l'ostacolo più a destra in ogni riga in un'iterazione della matrice data e possiamo trovare l'ostacolo più in basso in ogni colonna in un'altra iterazione della matrice data. Dopo aver memorizzato questi indici in un array separato, possiamo verificare su ciascun indice se non soddisfa o meno alcuna condizione di ostacolo e quindi aumentare il conteggio di conseguenza.
Di seguito è illustrata la soluzione implementata sul concetto precedente che richiede tempo O(N^2) e spazio aggiuntivo O(N).
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>
Produzione
2
Complessità temporale: O(n2).
Spazio ausiliario: O(n)