Я пишу программу на java и у меня есть матрица (0,1). Я хочу вычислить количество максимальных подпрямоугольников этого 2D-массива, состоящего только из нулей.
подпрямоугольник A является максимальным, если A не является подпрямоугольником большего подпрямоугольника B, так что B тоже состоит только из нулей.
Как мне подсчитывать такие подпрямоугольники?
У меня есть этот код, чтобы проверить, начинается ли подпрямоугольник размером высота * ширина с (вверху слева) есть только нули или нет, но я не знаю, что делать с максимальной частью:
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;
}
Например, для следующей матрицы ответом будет 3:
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
((1) прямоугольник 2 * 2, начинающийся с (0,0), (2) прямоугольник 2 * 5, начиная с (0,3) и (3) прямоугольник 1 * 8, начиная с (1,0))