39 lines
694 B
Go
39 lines
694 B
Go
// Package q3546 implements a solution for https://leetcode.com/problems/equal-sum-grid-partition-i/
|
|
package q3546
|
|
|
|
func chk(sums []int) bool {
|
|
sumAll := 0
|
|
for _, a := range sums {
|
|
sumAll += a
|
|
}
|
|
if sumAll%2 != 0 {
|
|
return false
|
|
}
|
|
|
|
target := sumAll / 2
|
|
sum := 0
|
|
for _, x := range sums {
|
|
sum += x
|
|
if sum == target {
|
|
return true
|
|
} else if sum > target {
|
|
return false
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
func canPartitionGrid(grid [][]int) bool {
|
|
hSums := make([]int, len(grid[0]))
|
|
vSums := make([]int, len(grid))
|
|
|
|
for r := range grid {
|
|
for c := range grid[0] {
|
|
hSums[c] += grid[r][c]
|
|
vSums[r] += grid[r][c]
|
|
}
|
|
}
|
|
return chk(hSums) || chk(vSums)
|
|
}
|
|
|
|
var _ = canPartitionGrid
|