grid[r][c] holds an integer score. Count the rectangular sub-blocks (any height and width of at least 1, fully inside the grid) whose total score is exactly target.
Examples
Input: grid = [[1, -1], [-1, 1]], target = 0
Output: 5
Explanation: both rows, both columns and the whole grid sum to 0; no single cell does.
Input: grid = [[2, 3], [4, 5]], target = 9
Output: 1
Explanation: only the bottom row 4 + 5 sums to 9.
Constraints
1 <= rows <= 30,1 <= cols <= 400-100 <= grid[r][c] <= 100,-10**6 <= target <= 10**6- Target complexity: O(rows^2 * cols). Checking all O(rows^2 * cols^2) rectangles by summing them is far too slow for the largest tests.
Goals
- Reduce a 2D counting problem to many 1D 'sum equals k' problems
- Collapse a band of rows into column sums incrementally