A square matrix is given in which each cell represents either a blank or an obstacle. We can place mirrors at blank position. All mirrors will be situated at 45 degree, i.e. they can transfer light from bottom to right if no obstacle is there in their path.
In this question we need to count how many such mirrors can be placed in square matrix which can transfer light from bottom to right.
Examples:
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 can solve this problem by checking position of such mirrors in matrix, the mirror which can transfer light from bottom to right will not have any obstacle in their path i.e.
if a mirror is there at index (i, j) then
there will be no obstacle at index (k, j) for all k, i < k <= N
there will be no obstacle at index (i, k) for all k, j < k <= N
Keeping above two equations in mind, we can find rightmost obstacle at every row in one iteration of given matrix and we can find bottommost obstacle at every column in another iteration of given matrix. After storing these indices in separate array we can check at each index whether it satisfies no obstacle condition or not and then increase the count accordingly.
Below is implemented solution on above concept which requires O(N^2) time and O(N) extra space.
C++
// C++ program to find how many mirror can transfer// light from bottom to right#include <bits/stdc++.h>using namespace std;// method returns number of mirror which can transfer// light from bottom to rightint 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 methodint 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 rightimport 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 codepublic 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 rightdef 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 methodN = 5;# B - Blank O - Obstaclemat = ["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 rightusing 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 codepublic 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 rightfunction 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 codevar N = 5;// B - Blank O - Obstaclevar mat = ["BBOBB", "BBBBO", "BBBBB", "BOOBO", "BBBOB"];document.write(maximumMirrorInMatrix(mat, N));</script> |
Output
2
Time complexity: O(n2).
Auxiliary Space: O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
