Number of cells in a matrix that satisfy the given condition | Python3 implementation of the approach ; Function to return the number of cells in which mirror can be placed ; Update the row array where row [ i ] [ j ] will store whether the current row i contains all 1 s in the columns starting from j ; Update the column array where col [ i ] [ j ] will store whether the current column j contains all 1 s in the rows starting from i ; To store the required result ; For every cell except the last row and the last column ; If the current cell is not blocked and the light can travel from the next row and the next column then the current cell is valid ; For the last column ; For the last row , note that the last column is not taken into consideration as the bottom right element has already been considered in the last column previously ; Driver code
N = 3 NEW_LINE def numberOfCells ( mat ) : NEW_LINE INDENT row = [ [ False for i in range ( N ) ] for i in range ( N ) ] NEW_LINE col = [ [ False for i in range ( N ) ] for i in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT if j + 1 < N : NEW_LINE INDENT row [ i ] [ j ] = row [ i ] [ j + 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT row [ i ] [ j ] = True NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT row [ i ] [ j ] = False NEW_LINE DEDENT DEDENT DEDENT for j in range ( N ) : NEW_LINE INDENT for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT if i + 1 < N : NEW_LINE INDENT col [ i ] [ j ] = col [ i + 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT col [ i ] [ j ] = True NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT col [ i ] [ j ] = False NEW_LINE DEDENT DEDENT DEDENT cnt = 0 NEW_LINE for i in range ( N - 1 ) : NEW_LINE INDENT for j in range ( N - 1 ) : NEW_LINE INDENT if ( row [ i ] [ j ] and col [ i ] [ j ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT if ( col [ i ] [ N - 1 ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT for j in range ( N - 1 ) : NEW_LINE INDENT if ( row [ N - 1 ] [ j ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT return cnt NEW_LINE DEDENT mat = [ [ 0 , 1 , 1 ] , [ 0 , 1 , 1 ] , [ 0 , 1 , 1 ] ] NEW_LINE print ( numberOfCells ( mat ) ) NEW_LINE