Подматрица заданного размера с максимумом единиц

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

Учитывая двоичную матрицу mat [] [] и целое число K , задача состоит в том, чтобы найти подматрицу размера K * K, такую, чтобы она содержала максимальное количество единиц в матрице.

Примеры:

Input: mat[][] = {{1, 0, 1}, {1, 1, 0}, {1, 0, 0}}, K = 2 
Output: 3 
Explanation: 
In the given matrix, there are 4 sub-matrix of order 2*2, 
|1 0| |0 1| |1 1| |1 0| 
|1 1|, |1 0|, |1 0|, |0 0| 
Out of these sub-matrix, two matrix contains 3, 1’s.

Input: mat[][] = {{1, 0}, {0, 1}}, K = 1 
Output: 1 
Explanation: 
In the given matrix, there are 4 sub-matrix of order 1*1, 
|1|, |0|, |1|, |0| 
Out of these sub-matrix, two matrix contains 1, 1’s. 

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

Подход: идея состоит в том, чтобы использовать метод скользящего окна для решения этой проблемы. В этом методе мы обычно вычисляем значение одного окна, а затем перемещаем окно одно за другим, чтобы вычислить решение для каждого окна размера K.
Чтобы вычислить подматрицу максимальной единицы, подсчитайте количество единиц в строке для каждого возможного окна размера K, используя технику скользящего окна, и сохраните количество единиц в форме матрицы.

Например:

 Пусть матрица имеет вид {{1,0,1}, {1, 1, 0}} и K = 2

Для строки 1 -
Подмассив 1: (1, 0), количество 1 = 1
Подмассив 2: (0, 1), количество 1 = 1

Для строки 2 -
Подмассив 1: (1, 1), количество 1 = 2
Подмассив 2: (1, 0), количество 1 = 1

Тогда окончательная матрица для подсчета единиц будет -
[1, 1]
[2, 1]

Точно так же примените метод скользящего окна к каждому столбцу этой матрицы, чтобы вычислить количество единиц в каждой возможной подматрице и извлечь максимум из этих подсчетов.

Below is the implementation of the above approach: 

C++

// C++ implementation to find the
// maximum count of 1"s in
// submatrix of order K
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// count of 1"s in the
// submatrix of order K
int maxCount(vector<vector<int>> &mat, int k) {
 
    int n = mat.size();
    int m = mat[0].size();
    vector<vector<int>> a;
 
    // Loop to find the count of 1"s
    // in every possible windows
    // of rows of matrix
    for (int e = 0; e < n; ++e){
        vector<int> s = mat[e];
        vector<int> q;
        int    c = 0;
         
        // Loop to find the count of
        // 1"s in the first window
        int i;
        for (i = 0; i < k; ++i)
            if(s[i] == 1)
                c += 1;
 
        q.push_back(c);
        int p = s[0];
         
        // Loop to find the count of
        // 1"s in the remaining windows
        for (int j = i + 1; j < m; ++j) {
            if(s[j] == 1)
                c+= 1;
            if(p == 1)
                c-= 1;
            q.push_back(c);
            p = s[j-k + 1];
        }
        a.push_back(q);
    }
 
    vector<vector<int>> b;
    int max = 0;
     
    // Loop to find the count of 1"s
    // in every possible submatrix
    for (int i = 0; i < a[0].size(); ++i) {
        int c = 0;
        int p = a[0][i];
         
        // Loop to find the count of
        // 1"s in the first window
        int j;
        for (j = 0; j < k; ++j) {
            c+= a[j][i];
        }
        vector<int> q;
        if (c>max)
            max = c;
        q.push_back(c);
         
        // Loop to find the count of
        // 1"s in the remaining windows
        for (int l = j + 1; j < n; ++j) {
            c+= a[l][i];
            c-= p;
            p = a[l-k + 1][i];
            q.push_back(c);
            if (c > max)
                max = c;
        }
 
        b.push_back(q);
    }
 
    return max;
}
 
// Driver code
int main()
{
    vector<vector<int>> mat = {{1, 0, 1}, {1, 1, 0}, {0, 1, 0}};
    int k = 3;
     
    // Function call
    cout<< maxCount(mat, k);
 
    return 0;
}

Java

// Java implementation to find the
// maximum count of 1"s in
// submatrix of order K
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to find the maximum
// count of 1"s in the
// submatrix of order K
static int maxCount(ArrayList<ArrayList<Integer> > mat, int k)
{
    int n = mat.size();
    int m = mat.get(0).size();
    ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
     
    // Loop to find the count of 1"s
    // in every possible windows
    // of rows of matrix
    for(int e = 0; e < n; ++e)
    {
        ArrayList<Integer> s = mat.get(e);
        ArrayList<Integer> q = new ArrayList<Integer>();
        int c = 0;
         
        // Loop to find the count of
        // 1"s in the first window
        int i;
        for(i = 0; i < k; ++i)
        {
            if (s.get(i) == 1)
            {
                c += 1;
            }
        }
        q.add(c);
        int p = s.get(0);
         
        // Loop to find the count of
        // 1"s in the remaining windows
        for(int j = i + 1; j < m; ++j)
        {
            if (s.get(j) == 1)
            {
                c += 1;
            }
            if (p == 1)
            {
                c -= 1;
            }
            q.add(c);
            p = s.get(j - k + 1);
        }
        a.add(q);
    }
     
    ArrayList<ArrayList<Integer>> b = new ArrayList<ArrayList<Integer>>();
    int max = 0;
     
    // Loop to find the count of 1"s
    // in every possible submatrix
    for(int i = 0; i < a.get(0).size(); ++i)
    {
        int c = 0;
        int p = a.get(0).get(i);
         
        // Loop to find the count of
        // 1"s in the first window
        int j;
        for(j = 0; j < k; ++j)
        {
            c += a.get(j).get(i);
        }
        ArrayList<Integer> q = new ArrayList<Integer>();
         
        if (c > max)
        {
            max = c;
        }
        q.add(c);
         
        // Loop to find the count of
        // 1"s in the remaining windows
        for(int l = j + 1; j < n; ++j)
        {
             
            c += a.get(l).get(i);
            c -= p;
            p = a.get(l - k + 1).get(i);
            q.add(c);
             
            if (c > max)
            {
                max = c;
            }
        }
        b.add(q);
    }
    return max;
}
 
// Driver code
public static void main(String[] args)
{
    ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();
    mat.add(new ArrayList<Integer>(Arrays.asList(1, 0, 1)));
    mat.add(new ArrayList<Integer>(Arrays.asList(1, 1, 0)));
    mat.add(new ArrayList<Integer>(Arrays.asList(0, 1, 0)));
    int k = 3;
     
    // Function call
    System.out.println(maxCount(mat, k));
}
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation to find the
# maximum count of 1"s in
# submatrix of order K
 
# Function to find the maximum
# count of 1"s in the
# submatrix of order K
def maxCount(mat, k):
    n, m = len(mat), len(mat[0])
    a =[]
     
    # Loop to find the count of 1"s
    # in every possible windows
    # of rows of matrix
    for e in range(n):
        s = mat[e]
        q =[]
        c = 0
         
        # Loop to find the count of
        # 1"s in the first window
        for i in range(k):
            if s[i] == 1:
                c += 1
        q.append(c)
        p = s[0]
         
        # Loop to find the count of
        # 1"s in the remaining windows
        for j in range(i + 1, m):
            if s[j]==1:
                c+= 1
            if p ==1:
                c-= 1
            q.append(c)
            p = s[j-k + 1]
        a.append(q)
    b =[]
    max = 0
     
    # Loop to find the count of 1"s
    # in every possible submatrix
    for i in range(len(a[0])):
        c = 0
        p = a[0][i]
         
        # Loop to find the count of
        # 1"s in the first window
        for j in range(k):
            c+= a[j][i]
        q =[]
        if c>max:
            max = c
        q.append(c)
         
        # Loop to find the count of
        # 1"s in the remaining windows
        for l in range(j + 1, n):
            c+= a[l][i]
            c-= p
            p = a[l-k + 1][i]
            q.append(c)
            if c > max:
                max = c
        b.append(q)
    return max
     
# Driver Code
if __name__ == "__main__":
    mat = [[1, 0, 1], [1, 1, 0], [0, 1, 0]]
    k = 3
     
    # Function call
    print(maxCount(mat, k))

C#

// C# implementation to find the
// maximum count of 1"s in
// submatrix of order K
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the maximum
// count of 1"s in the
// submatrix of order K
static int maxCount(List<List<int>> mat, int k)
{
    int n = mat.Count;
    int m = mat[0].Count;
    List<List<int>> a = new List<List<int>>();
     
    // Loop to find the count of 1"s
    // in every possible windows
    // of rows of matrix
    for(int e = 0; e < n; ++e)
    {
        List<int> s = mat[e];
        List<int> q = new List<int>();
        int c = 0;
         
        // Loop to find the count of
        // 1"s in the first window
        int i;
         
        for(i = 0; i < k; ++i)
        {
            if (s[i] == 1)
            {
                c++;
            }
        }
        q.Add(c);
        int p = s[0];
         
        // Loop to find the count of
        // 1"s in the remaining windows
        for(int j = i + 1; j < m; ++j)
        {
            if (s[j] == 1)
            {
                c++;
            }
            if (p == 1)
            {
            &nb
Олимпиады по программированию

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

Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Минимизируйте длину массива, многократно удаляя элементы, которые меньше, чем следующий элемент
19 Сентября, 2022
Задача коммивояжера Bitonic
19 Сентября, 2022
Количество суперстрок в заданном массиве строк
19 Сентября, 2022
Количество чередующихся подстрок из заданной двоичной строки
19 Сентября, 2022
Максимальное удаление мячей как минимум двух разных типов
19 Сентября, 2022
Общее время, необходимое для прохождения пути, обозначенного данной строкой
19 Сентября, 2022
Советы и рекомендации Python для соревновательного программирования
19 Сентября, 2022