Number of Submatrices that Sum to Target

Count the nonempty rectangular submatrices of matrix whose cell values sum to target. A submatrix selects a consecutive range of rows and a consecutive range of columns. Rectangles with different boundaries count separately, even if they contain the same values. Return the total count.

Example 1:

Input: matrix = [[1,1],[1,1]]
target = 2

Output: 4

Explanation: Each complete row and each complete column contains two 1s and sums to 2. These four rectangles qualify; individual cells sum to 1 and the whole matrix sums to 4.

Example 2:

Input: matrix = [[0,0]]
target = 0

Output: 3

Explanation: Each of the two individual zero cells is a valid rectangle, and the rectangle covering both cells also sums to zero. The total count is 3.

Example 3:

Input: matrix = [[2,-2],[3,-3]]
target = 0

Output: 3

Explanation: The top row, the bottom row, and the entire matrix each sum to zero. No single cell or single-column rectangle does, so the count is 3.

Constraints:

• matrix is rectangular, with between 1 and 100 rows and between 1 and 100 columns.
• -1000 <= matrix[i][j] <= 1000
• -100000000 <= target <= 100000000