we were discussing a problem of finding the largest submatrix of 1 in a boolean matrix.
Another technique is to not divide the matrix into equal parts over and over again but to use a graph and traversal algorithms to find islands. Then for each of these islands find the largest size.
this is therefore a two step procedure.
first, we do a depth first traversal. here we only recurse if the cordinate is safe. by that we mean the points are within the matrix boundaries, are all ones and they have not been visited. we keep a visited matrix which we fill and we can explore all eight adjacencies of a point one at a time. if a cell with value 1 is not visited then we found a new island and make note of this cordinate.
Another technique is to not divide the matrix into equal parts over and over again but to use a graph and traversal algorithms to find islands. Then for each of these islands find the largest size.
this is therefore a two step procedure.
first, we do a depth first traversal. here we only recurse if the cordinate is safe. by that we mean the points are within the matrix boundaries, are all ones and they have not been visited. we keep a visited matrix which we fill and we can explore all eight adjacencies of a point one at a time. if a cell with value 1 is not visited then we found a new island and make note of this cordinate.
- second for each island and a cordinate on this island, we can explore its size and the maximum submatrix rectangle contained by any of the techniques mentioned earlier such as the histogram method. This gives us the cordinates and the size of the final submatrix we are interested in.
No comments:
Post a Comment