51 lines
979 B
Go
51 lines
979 B
Go
package q1292
|
|
|
|
func pfSum(mat [][]int) [][]int {
|
|
w, h := len(mat[0])+1, len(mat)+1
|
|
pfs := make([][]int, h)
|
|
for i := range pfs {
|
|
pfs[i] = make([]int, w)
|
|
}
|
|
|
|
for y := 1; y < h; y++ {
|
|
for x := 1; x < w; x++ {
|
|
pfs[y][x] = mat[y-1][x-1] + pfs[y][x-1] + pfs[y-1][x] - pfs[y-1][x-1]
|
|
}
|
|
}
|
|
return pfs
|
|
}
|
|
|
|
func sumOfSquare(pfs [][]int, x, y, w int) int {
|
|
return pfs[y+w][x+w] - pfs[y][x+w] - pfs[y+w][x] + pfs[y][x]
|
|
}
|
|
|
|
func hasSquare(pfs [][]int, edgeLen, threshold int) bool {
|
|
w, h := len(pfs[0])-1, len(pfs)-1
|
|
for y := range h - edgeLen + 1 {
|
|
for x := range w - edgeLen + 1 {
|
|
if sumOfSquare(pfs, x, y, edgeLen) <= threshold {
|
|
return true
|
|
}
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
func maxSideLength(mat [][]int, threshold int) int {
|
|
pfs := pfSum(mat)
|
|
w, h := len(pfs[0]), len(pfs)
|
|
maxAllowed := min(w, h)
|
|
|
|
l, r := 0, maxAllowed+1
|
|
for l+1 < r {
|
|
m := (l + r) / 2
|
|
if hasSquare(pfs, m, threshold) {
|
|
l = m
|
|
} else {
|
|
r = m
|
|
}
|
|
}
|
|
return l
|
|
}
|
|
|
|
var _ = maxSideLength
|