Проверьте, производит ли перестановка строк или столбцов двоичную подматрицу максимального размера со всеми единицами

Опубликовано: 20 Января, 2022

Учитывая двоичную матрицу, задача состоит в том, чтобы определить, дает ли перестановка строк или столбцов подматрица максимального размера со всеми единицами. При замене строк мы можем менять местами любые две строки. При обмене столбцами мы можем менять местами любые два столбца. Выведите «Обмен строк» или «Обмен столбцов» и максимальный размер.

Примеры:

Ввод: 1 1 1
        1 0 1
Вывод: замена столбцов
         4
Поменяв местами столбец 1 и столбец 2 (индексирование на основе 0), 
index (0, 0) to (1, 1) делает наибольший двоичный 
подматрица.

Ввод: 0 0 0
        1 1 0
        1 1 0
        0 0 0
        1 1 0 
Вывод: замена строк
         6

Ввод: 1 1 0
        0 0 0
        0 0 0
        1 1 0
        1 1 0
        0 0 0
        1 1 0 
Вывод: замена строк
         8

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы найти двоичную подматрицу максимального размера подкачки строк и столбцов и сравнить.

Чтобы найти двоичную подматрицу максимального размера с допустимой перестановкой строк, создайте двумерный массив, скажем, dp [i] [j]. Каждое значение dp [i] [j] содержит количество последовательных единиц справа от (i, j) в i-й строке. Теперь сохраните каждый столбец в одномерном временном массиве один за другим, скажем, b [], выполните сортировку и найдите максимальное значение b [i] * (n - i), поскольку b [i] указывает ширину подматрицы и (n - i) - высота подматрицы.

Точно так же, чтобы найти двоичную подматрицу максимального размера с разрешенной перестановкой столбцов, найдите dp [i] [j], где каждое значение содержит номер последовательной 1 под (i, j) в j-м столбце. Аналогичным образом сохраните каждую строку в одномерном временном массиве одну за другой, скажем, b [], и выполните сортировку. Найдите максимальное значение b [i] * (m - i), поскольку b [i] указывает высоту подматрицы, а (n - i) - ширину подматрицы.

Below is the implementation of this approach:

C++

// C++ program to find maximum binary sub-matrix
// with row swaps and column swaps.
#include <bits/stdc++.h>
#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<R; ++i)
        {
            // If (i,j) contain 0, do nothing
            if (mat[i][j] == 0)
                ryt[i][j] = 0;
  
            // Counting consecutive 1 on right side
            else
                ryt[i][j] = ryt[i][j + 1] + 1;
        }
    }
  
  
    // Travesing the 2d matrix from bottom-left.
    for (int i = R - 1; 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<C; j++)
    {
        // Copying the column
        for (int i=0; i<R; i++)
            b[i] = ryt[i][j];
  
        // Sort the copied array
        sort(b, b + R);
  
        // Find maximum submatrix size.
        for (int i = 0; i < R; ++i)
            ans = max(ans, b[i] * (R - i));
    }
  
    return ans;
}
  
// Return maximum size submatrix with column
// swap allowed.
int solveColumnSwap(int dwn[R + 2][C + 2])
{
    int b[C] = { 0 }, ans = 0;
  
    for (int i = 0; i < R; ++i)
    {
        // Copying the row.
        for (int j = 0; j < C; ++j)
            b[j] = dwn[i][j];
  
        // Sort the copied array
        sort(b, b + C);
  
        // Find maximum submatrix size.
        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);
  
    // Solving for row swap and column swap
    int rswap = solveRowSwap(ryt);
    int cswap = solveColumnSwap(dwn);
  
    // Comparing both.
    (rswap > cswap)? (cout << "Row Swap " << rswap << endl):
                     (cout << "Column Swap " << 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;
}

Java

import java.util.Arrays;
  
// Java program to find maximum binary sub-matrix
// with row swaps and column swaps.
class GFG {
  
    static int R = 5;
    static int C = 3;
  
// 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.
    static void precompute(int mat[][], int ryt[][],
            int dwn[][]) {
        // Travesing the 2d matrix from top-right.
        for (int j = C - 1; j >= 0; j--) {
            for (int i = 0; i < R; ++i) {
                // If (i,j) contain 0, do nothing
                if (mat[i][j] == 0) {
                    ryt[i][j] = 0;
                } // Counting consecutive 1 on right side
                else {
                    ryt[i][j] = ryt[i][j + 1] + 1;
                }
            }
        }
  
        // Travesing the 2d matrix from bottom-left.
        for (int i = R - 1; 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.
    static int solveRowSwap(int ryt[][]) {
        int b[] = new int[R], ans = 0;
  
        for (int j = 0; j < C; j++) {
            // Copying the column
            for (int i = 0; i < R; i++) {
                b[i] = ryt[i][j];
            }
  
            // Sort the copied array
            Arrays.sort(b);
  
            // Find maximum submatrix size.
            for (int i = 0; i < R; ++i) {
                ans = Math.max(ans, b[i] * (R - i));
            }
        }
  
        return ans;
    }
  
// Return maximum size submatrix with column
// swap allowed.
    static int solveColumnSwap(int dwn[][]) {
        int b[] = new int[C], ans = 0;
  
        for (int i = 0; i < R; ++i) {
            // Copying the row.
            for (int j = 0; j < C; ++j) {
                b[j] = dwn[i][j];
            }
  
            // Sort the copied array
            Arrays.sort(b);
  
            // Find maximum submatrix size.
            for (int k = 0; k < C; ++k) {
                ans = Math.max(ans, b[k] * (C - k));
            }
        }
  
        return ans;
    }
  
    static void findMax1s(int mat[][]) {
        int ryt[][] = new int[R + 2][C + 2], dwn[][] = new int[R + 2][C + 2];
  
        precompute(mat, ryt, dwn);
  
        // Solving for row swap and column swap
        int rswap = solveRowSwap(ryt);
        int cswap = solveColumnSwap(dwn);
  
        // Comparing both.
        if (rswap > cswap) {
            System.out.println("Row Swap " + rswap);
        } else {
            System.out.println("Column Swap " + cswap);
        }
    }
  
// Driven Program 
    public static void main(String[] args) {
        int mat[][] = {{0, 0, 0},
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 0},
        {1, 1, 0}};
  
        findMax1s(mat);
    }
}
  
/* This Java code is contributed by PrinciRaj1992*/

Python3

# Python3 program to find maximum binary
# sub-matrix with row swaps and column swaps.
R, C = 5, 3
  
# 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.
def precompute(mat, ryt, dwn):
  
    # Travesing the 2d matrix from top-right.
    for j in range(C - 1, -1, -1):
      
        for i in range(0, R):
          
            # If (i,j) contain 0, do nothing
            if mat[i][j] == 0:
                ryt[i][j] = 0
  
            # Counting consecutive 1 on right side
            else:
                ryt[i][j] = ryt[i][j + 1] + 1
          
    # Travesing the 2d matrix from bottom-left.
    for i in range(R - 1, -1, -1):
      
        for j in range(0, C):
          
            # 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.
def solveRowSwap(ryt):
  
    b = [0] * R
    ans = 0
  
    for j in range(0, C):
      
        # Copying the column
        for i in range(0, R):
            b[i] = ryt[i][j]
  
        # Sort the copied array
        b.sort()
  
        # Find maximum submatrix size.
        for i in range(0, R):
            ans = max(ans, b[i] * (R - i))
      
    return ans
  
# Return maximum size submatrix
# with column swap allowed.
def solveColumnSwap(dwn):
  
    b = [0] * C
    ans = 0
  
    for i in range(0, R):
      
        # Copying the row.
        for j in range(0, C):
            b[j] = dwn[i][j]
  
        # Sort the copied array
        b.sort()
  
        # Find maximum submatrix size.
        for i in range(0, C):
            ans = max(ans, b[i] * (C - i))
      
    return ans
  
def findMax1s(mat):
  
    ryt = [[0 for i in range(C + 2)] 
              for j in range(R + 2)]
    dwn = [[0 for i in range(C + 2)] 
              for j in range(R +

РЕКОМЕНДУЕМЫЕ СТАТЬИ