Maximum mirrors which can transfer light from bottom to right | C ++ 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 ; To store first obstacles horizontaly ( from right ) and vertically ( from bottom ) ; initialize both array as - 1 , signifying no obstacle ; looping matrix to mark column for obstacles ; mark rightmost column with obstacle ; looping matrix to mark rows for obstacles ; mark leftmost row with obstacle ; Initialize result ; if there is not obstacle on right or below , then mirror can be placed to transfer light ; if i > vertical [ j ] then light can from bottom if j > horizontal [ i ] then light can go to right ; uncomment this code to print actual mirror position also cout << i << " ▁ " << j << endl ; ; Driver code to test above method ; B - Blank O - Obstacle
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumMirrorInMatrix ( string mat [ ] , int N ) { int horizontal [ N ] , vertical [ N ] ; memset ( horizontal , -1 , sizeof ( horizontal ) ) ; memset ( vertical , -1 , sizeof ( vertical ) ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N - 1 ; j >= 0 ; j -- ) { if ( mat [ i ] [ j ] == ' B ' ) continue ; horizontal [ i ] = j ; break ; } } for ( int j = 0 ; j < N ; j ++ ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( mat [ i ] [ j ] == ' B ' ) continue ; vertical [ j ] = i ; break ; } } int res = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( i > vertical [ j ] && j > horizontal [ i ] ) { res ++ ; } } } return res ; } int main ( ) { int N = 5 ; string mat [ N ] = { " BBOBB " , " BBBBO " , " BBBBB " , " BOOBO " , " BBBOB " } ; cout << maximumMirrorInMatrix ( mat , N ) << endl ; return 0 ; }