Square Plots Under the Rock Limit

A field is given as a list of equal-length strings field, where '.' is grass and '*' is a rock. A square plot is an s x s block of cells (s >= 1) lying fully inside the field. Return the number of square plots, over all positions and all sizes, that contain at most t rocks.

Examples

Input:  field = ["..*", "...", "*.."], t = 0
Output: 9
Explanation: seven grass cells, plus the 2x2 blocks with top-left corners (0, 0) and (1, 1).

Input:  field = ["..*", "...", "*.."], t = 1
Output: 13
Explanation: all nine cells and all four 2x2 blocks; the whole field holds two rocks.

Input:  field = ["*"], t = 0
Output: 0

Constraints

• 1 <= len(field), len(field[0]) <= 300
• 0 <= t <= 10**5
• The largest tests are 300 x 300 fields with big qualifying squares; growing a square one size at a time from every corner is too slow.

Goals

• Count the rocks in any square in O(1) with a 2D prefix-sum table
• Notice that the best size can shrink by at most 1 along a diagonal
• Share work between neighbouring corners instead of starting over