Example 73: Largest Square Submatrix with All 1s
Explore how to determine the largest square submatrix filled with all 1s in a given 0-1 matrix. This lesson guides you through using an auxiliary matrix to track submatrix sizes and understand the dynamic programming approach to efficiently solve this problem involving multi-dimensional arrays.
We'll cover the following...
We'll cover the following...
Problem
Given a matrix that contains only 1s and/or 0s, write a program to obtain the order of the largest square submatrix with all 1s.
Example
| Input | Output |
|---|---|
| 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 |
3 |
| 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 |
1 |
Try it yourself
Try to solve this ...