改变矩阵列并得到所有元素都相等的子矩阵的行数

Question

我有一个矩阵。它只能包含 0 和 1。示例:

1 0 1 0 1

1 0 1 0 1

1 1 1 1 1

0 0 0 0 1

1 1 1 1 1

0 0 0 1 0

0 1 0 0 0

我需要显示所有元素 = 0 的子矩阵(m 行和 m 列 - m x m)的最大行数。该程序可以更改矩阵列的顺序。

我是C初学者，不知道如何开始。

Answer 1

你提到的问题可以称为最大方 block 问题

您可以找到与此相关的多个主题及其解决方案:

Dynamic programming - Largest square block

Find largest rectangle containing only zeros in an N×N binary matrix

Maximize the rectangular area under Histogram

Finding maximum size sub-matrix of all 1's in a matrix having 1's and 0's

这里是我为此完成的一个 C 函数，数组 grid 被展平，如您所见，我使用了一个 counter 数组:

typedef struct s_max
{
    t_uint16 val_max_;
    t_uint16 idx_max_;
} t_max;

t_max largest_square_block(t_uint8 *grid, const t_uint16 h, const t_uint16 w)
{
    t_uint16 up, upleft, left;
    t_uint16 val_max = 0;
    t_uint16 idx_max = 0;

    t_uint16 *counter = (t_uint16 *) malloc(w * h * sizeof(t_uint16));
    counter[0] = grid[0];

    for (t_uint i = 1; i < w * h; i ++)
    {   
        up = upleft = left = 0;
        if (grid[i] != YOURMAGICNUMBER)
        {
            if (i >= w)
                up = counter[i - w];
            if (i % w > 0)
            {
                left = counter[i - 1];
                if (i >= w)
                    upleft = counter[i - 1 - w];
            }
            counter[i] = 1 + min3_uint16(up, upleft, left);
            if (counter[i] > val_max)
            {
                val_max = counter[i];
                idx_max = i;
            }

        }
    }

    free(counter);

    t_max data_max;
    data_max.val_max_ = val_max;
    data_max.idx_max_ = idx_max;

    return data_max;
}