# Biggest surface in a matrix

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

## 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 on other sites
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 on other sites
Actually this is part of a project I decided to take part of. And yes, it is about a rectangular sub-matrix.

##### Share on other sites
Pseudo code for a brute force solution:

current biggest = 0for 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.

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 9
• 12
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
633348
• Total Posts
3011459
• ### Who's Online (See full list)

There are no registered users currently online

×