Jump to content
  • Advertisement
Sign in to follow this  

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.

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

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!