KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Given a binary matrix, I have find out the maximum size square sub-matrix with all 1 s. For example, consider the below binary matrix: 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The maximum square sub-matrix with all set bits is 1 1 1 1 1 1 1 1 1 I searched the web for solutions and I found a relation to construct an auxiliary matrix: If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 Where M[][] is the original matrix and s[][] is the auxiliary matrix? What does this relation signify? And how is it helpful.
Tags (comma-separated)
Save Edits
Cancel