Biggest surface in a matrix
Author
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
A couple of questions:
1. Is this a homework assignment?
2. What's the definition of a 'surface'? Is it a rectangular sub-matrix?
1. Is this a homework assignment?
2. What's the definition of a 'surface'? Is it a rectangular sub-matrix?
Author
Actually this is part of a project I decided to take part of. And yes, it is about a rectangular sub-matrix.
Pseudo code for a brute force solution:
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.
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.
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 biggestAnd 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 lengthThere 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
