• Advertisement
Sign in to follow this  

Biggest surface in a matrix

This topic is 3002 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone, I am new around here. In my program, I have a random matrix M x N which contains only 1 and 0. What I want to do is to search the matrix for the biggest surface of 1. For example: 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 => biggest surface is 6 or if: 1 0 1 0 1 1 0 1 1 0 0 1 => biggest surface is 2 Can someone please give me any ideas or some code for this in vb net ? thanks in advance, Luc

Share this post


Link to post
Share on other sites
Advertisement
A couple of questions:

1. Is this a homework assignment?

2. What's the definition of a 'surface'? Is it a rectangular sub-matrix?

Share this post


Link to post
Share on other sites
Pseudo code for a brute force solution:


current biggest = 0
for each element in the matrix.
if element = 1
call check_size of sub matrix with this as top left
if this is the biggest then store it as the current biggest


And then code to check the size of the submatrix:

Pretend that we have the sub matrix as a new matrix here. Could just pass the i,j indices of the top left and adjust accordingly.

for each row
for each column
if value at current row column is 0 then stop processing row and store the number of values checked as current_row_length.
if current_row_length is 0 then stop function and return min row length * number of rows processed - 1
else if current row length < min row length store current row length AS min row length


There is a vast amount of optimisation and correction (probably) required to the above.

It is an interesting problem though. I wonder whether it is a necessarily polynomial time problem.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement