// C++ program to find maximum binary sub-matrix // with row swaps and column swaps. #include #define R 5 #define C 3 using namespace std; // Precompute the number of consecutive 1 below the // (i, j) in j-th column and the number of consecutive 1s // on right side of (i, j) in i-th row. void precompute(int mat[R][C], int ryt[][C + 2], int dwn[R + 2][C + 2]) { // Travesing the 2d matrix from top-right. for (int j=C-1; j>=0; j--) { for (int i=0; i= 0; i--) { for (int j = 0; j < C; ++j) { // If (i,j) contain 0, do nothing if (mat[i][j] == 0) dwn[i][j] = 0; // Counting consecutive 1 down to (i,j). else dwn[i][j] = dwn[i + 1][j] + 1; } } } // Return maximum size submatrix with row swap allowed. int solveRowSwap(int ryt[R + 2][C + 2]) { int b[R] = { 0 }, ans = 0; for (int j=0; j cswap)? (cout << "Row Swap\n" << rswap << endl): (cout << "Column Swap\n" << cswap << endl); } // Driven Program 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; }