Change matrix columns and get the number of lines of a sub-matrix with all elements equals

Question

I have a matrix. It could contain only 0 and 1. Example:

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

I need to show the maximum number of lines, of a sub-matrix (m lines and m columns - m x m) which has all elements = 0. The program can change the order of matrix columns.

I am a beginner of C and I don't know how to start.

What have you tried so far ? For someone with >1k, it looks like your first times here... — coincoin, Nov 12 '15 at 08:32
As I said I am a beginner. I tried some things but with no result. All I tried doesn't work. I tried to determine the number of elements with 0 on each line, and for each tried to check if there are elements on the next line on the same position which are zero, but this can't work, because I will need to verify pairs of columns if are 0 and I don't know how to do. — MM PP, Nov 12 '15 at 08:40
At least, provide some code and show your work. How do you store your matrix for instance ? — coincoin, Nov 12 '15 at 08:42
`of a sub-matrix (m lines and m columns - m x m) ` means the row and column sub-matrix are equals? That is to say a n * m(n != m) sub-matrix is invalid? — Sayakiss, Nov 12 '15 at 08:50

score 1 · Accepted Answer · edited May 23 '17 at 12:30

The problem you mention can be known as the Largest Square Block Problem

You can find several topics related to this with solutions :

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

Here a C function I have done for that, array grid is flatten as you see and I use a counter array :

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;
}

Change matrix columns and get the number of lines of a sub-matrix with all elements equals

1 Answers1