Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
Solution:
func getMin (a, b,c byte) byte {
min := a
if min > b{
min = b
}
if min > c {
min = c
}
return min
}
// DP to find edge
func maximalSquare(matrix [][]byte) int {
lenN := len(matrix);
if lenN == 0 {
return 0
}
lenM := len(matrix[0]);
dp :=[][]byte{};
maxEdge:= 0 //!!
for i := 0; i < lenN ; i++ {
dp = append(dp, make([]byte,lenM))
}
for x := 0; x < lenN ; x++ {
for y:=0; y < lenM; y++ {
if x == 0 || y == 0 {
v:= matrix[x][y] - '0'
dp[x][y] =v // !important
}else {
if matrix[x][y] - '0' > 0 {
min := getMin(dp[x-1][y-1], dp[x-1][y], dp[x][y-1]) //!important
dp[x][y] = min + 1
}else {
dp[x][y] = 0
}
}
if (int(dp[x][y] )> maxEdge) {
maxEdge = int(dp[x][y])
}
}
}
return maxEdge * maxEdge
}