Как найти подматрицу хотя бы с k 1 с? - PullRequest
Новая
       20

Как найти подматрицу хотя бы с k 1 с?

0 голосов
/ 27 февраля 2020

У меня есть квадратная матрица размера n с 1 и 0, и мне нужно найти размер стороны наименьшей квадратной подматрицы, которая содержит не менее k 1. Если входное значение равно: n = 5 и k = 3 с матрицей: 

0 1 1 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0

Выходное значение должно быть 3, поскольку наименьшая квадратная подматрица, содержащая не менее 3 1 с, - это та, которая начинается с (1 1 ) и заканчивается в (3 3). Я сделал это, но я хочу уменьшить O (n³) до O (n²) 

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin("input.in");
ofstream fout("output.out");

int a[1001][1001], n, k;

void sum(){
    int i, j;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}

void solve(){
    int i, j, ii, jj, x, minim=1e9, val=0, side=1e9, ok;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            for (x=0;x<n;x++){
                ii=i+x;
                jj=j+x;
                if (ii<=n&&jj<=n){
                    val=a[ii][jj]-a[i-1][jj]-a[ii][j-1]+a[i-1][j-1];
                    if (val>=k)
                        side=min(side, x+1);
                }
            }
        }
    fout<<side;
}
...