时间戳

首页 > 解决方案 > 子矩形的数量

java - 子矩形的数量

问题描述

我在java中有一个m * n 2D数组，使得这个数组的一些元素等于1，一些元素等于0。我想找到这个二维数组的子矩形的数量，其中 k 区域仅由零组成。我应该怎么办？

例如对于下面的数组，这个 2D 数组的子矩形数量为 11，其中区域 2 仅由零组成。

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 的子矩形，但我发现这很困难。

标签： javaarrays

解决方案

countSubRectangles计算heightx 个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

推荐阅读