Maximum mirrors which can transfer light from bottom to right - GeeksforGeeks
A square matrix is given in which each cell represents either a blank or an obstacle. We can place mirrors at blank positionl. 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.
Read full article from Maximum mirrors which can transfer light from bottom to right - GeeksforGeeks
A square matrix is given in which each cell represents either a blank or an obstacle. We can place mirrors at blank positionl. 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.
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.
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.
// method returns number of mirror which can transfer
// light from bottom to right
int
maximumMirrorInMatrix(string mat[],
int
N)
{
// To store first obstacles horizontaly (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;
}