Region Target Sums
Hard · prefix sum
A market hall is laid out as a grid of stalls. The grid ledger has one row per row of stalls, and ledger[r][c] is the result of the stall in row r, column c for the day: positive for a profit, negative for a loss, and zero for breaking even.
A region is a block of stalls made of whole cells that fills a rectangle: it covers some run of neighbouring rows and some run of neighbouring columns, and contains every stall inside that rectangle. A single stall is also a region.
Return how many regions have a total result of exactly target. Regions are told apart by their position, not their values, so two regions with the same values in different places each count. If there are none, return 0.
Examples
Example 1
Input: ledger = [[1, 2], [3, 4]], target = 3
Output: 2
The top row (1 + 2) and the single stall 3 both total 3.
Example 2
Input: ledger = [[0, 0], [0, 0]], target = 0
Output: 9
Every region totals 0. There are 3 ways to choose the rows and 3 ways to choose the columns.
Example 3
Input: ledger = [[1, -1], [-1, 1]], target = 0
Output: 5
The two rows, the two columns and the whole grid each total 0. No single stall does.
Constraints
- 1 <= rows, columns <= 50, and every row of ledger has the same length
- -100 <= ledger[r][c] <= 100
- -10^6 <= target <= 10^6