количество суб прямоугольников

Question

У меня есть 2D-массив m * n в java, так что некоторые элементы этого массива равны единице, а некоторые равны нулю. Я хочу найти количество субпрямоугольников этого 2D-массива с площадью k, состоящей только из нулей. Что мне делать?

например, для следующего массива количество субпрямоугольников этого 2D-массива с областью 2, состоящей только из нулей, равно 11.

1 0 0 0 1 0 0 0

0 1 0 1 0 1 0 1

0 0 1 0 0 0 1 0

Моя идея заключалась в том, чтобы подсчитать все суб прямоугольники с площадью k, а затем опустить те, которые состоят из 1, но я нашел это затруднительным.

Answer 1

countSubRectangles подсчитывает height x width прямоугольников.

static boolean areAllZeros(int[][] matrix, int top, int left, int height, int width) {
    int maxHeight = matrix.length;
    int maxWidth = matrix[0].length;
    int bottom = top + height;
    int right = left + width;
    if (bottom > maxHeight || right > maxWidth)
        return false;
    for (int i = top; i < bottom; ++i)
        for (int j = left; j < right; ++j)
            if (matrix[i][j] != 0)
                return false;
    return true;
}

static int countSubRectangles(int[][] matrix, int height, int width) {
    int maxHeight = matrix.length;
    int maxWidth = matrix[0].length;
    int count = 0;
    for (int i = 0; i < maxHeight; ++i)
        for (int j = 0; j < maxWidth; ++j)
            if (areAllZeros(matrix, i, j, height, width))
                ++count;
    return count;
}

и

int[][] matrix = {
    {1, 0, 0, 0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0, 1, 0, 1},
    {0, 0, 1, 0, 0, 0, 1, 0},
};
System.out.println(
    countSubRectangles(matrix, 1, 2)      // count 1x2 sub rectangles
    + countSubRectangles(matrix, 2, 1));  // count 2x1 sub rectangles
// -> 11

Answer 2

Вам нужно посчитать каждый субпрямоугольник с площадью > = k . В соответствии с вашим описанием в подпрямоугольнике допускается 1. Мое предложение таково:

for(int height=1; height<m; height++)
    for(int width=1; width<n && width>=k/height; width++)
        for(int y=0; y+height<=m; y++)
            for(int x=0; x+width<=n; x++){
                // check if the sub rectangle (x, y)-(x+width-1, y+height-1) contains k zeros
            }