Check whether row or column swaps produce maximum size binary sub | C ++ program to find maximum binary sub - matrix with row swaps and column swaps . ; Precompute the number of consecutive 1 below the ( i , j ) in j - th column and the number of consecutive 1 s on right side of ( i , j ) in i - th row . ; Travesing the 2d matrix from top - right . ; If ( i , j ) contain 0 , do nothing ; Counting consecutive 1 on right side ; Travesing the 2d matrix from bottom - left . ; If ( i , j ) contain 0 , do nothing ; Counting consecutive 1 down to ( i , j ) . ; Return maximum size submatrix with row swap allowed . ; Copying the column ; Sort the copied array ; Find maximum submatrix size . ; Return maximum size submatrix with column swap allowed . ; Copying the row . ; Sort the copied array ; Find maximum submatrix size . ; Solving for row swap and column swap ; Comparing both . ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define R  5 NEW_LINE #define C  3 NEW_LINE using namespace std ; void precompute ( int mat [ R ] [ C ] , int ryt [ ] [ C + 2 ] , int dwn [ R + 2 ] [ C + 2 ] ) { for ( int j = C - 1 ; j >= 0 ; j -- ) { for ( int i = 0 ; i < R ; ++ i ) { if ( mat [ i ] [ j ] == 0 ) ryt [ i ] [ j ] = 0 ; else ryt [ i ] [ j ] = ryt [ i ] [ j + 1 ] + 1 ; } } for ( int i = R - 1 ; i >= 0 ; i -- ) { for ( int j = 0 ; j < C ; ++ j ) { if ( mat [ i ] [ j ] == 0 ) dwn [ i ] [ j ] = 0 ; else dwn [ i ] [ j ] = dwn [ i + 1 ] [ j ] + 1 ; } } } int solveRowSwap ( int ryt [ R + 2 ] [ C + 2 ] ) { int b [ R ] = { 0 } , ans = 0 ; for ( int j = 0 ; j < C ; j ++ ) { for ( int i = 0 ; i < R ; i ++ ) b [ i ] = ryt [ i ] [ j ] ; sort ( b , b + R ) ; for ( int i = 0 ; i < R ; ++ i ) ans = max ( ans , b [ i ] * ( R - i ) ) ; } return ans ; } int solveColumnSwap ( int dwn [ R + 2 ] [ C + 2 ] ) { int b [ C ] = { 0 } , ans = 0 ; for ( int i = 0 ; i < R ; ++ i ) { for ( int j = 0 ; j < C ; ++ j ) b [ j ] = dwn [ i ] [ j ] ; sort ( b , b + C ) ; for ( int i = 0 ; i < C ; ++ i ) ans = max ( ans , b [ i ] * ( C - i ) ) ; } return ans ; } void findMax1s ( int mat [ R ] [ C ] ) { int ryt [ R + 2 ] [ C + 2 ] , dwn [ R + 2 ] [ C + 2 ] ; memset ( ryt , 0 , sizeof ryt ) ; memset ( dwn , 0 , sizeof dwn ) ; precompute ( mat , ryt , dwn ) ; int rswap = solveRowSwap ( ryt ) ; int cswap = solveColumnSwap ( dwn ) ; ( rswap > cswap ) ? ( cout << " Row ▁ Swap STRNEWLINE " << rswap << endl ) : ( cout << " Column ▁ Swap STRNEWLINE " << cswap << endl ) ; } int main ( ) { int mat [ R ] [ C ] = { { 0 , 0 , 0 } , { 1 , 1 , 0 } , { 1 , 1 , 0 } , { 0 , 0 , 0 } , { 1 , 1 , 0 } } ; findMax1s ( mat ) ; return 0 ; }