Count Valid T Shapes in a Binary Matrix

This problem asks you to count the number of valid T shapes in a given binary matrix. A T shape consists of a horizontal segment and a vertical segment arranged like the letter T. The horizontal segment (denoted as “\(\text{横}\)”) and the vertical segment (denoted as “\(\text{竖}\)”) share a common cell which is counted in both segments.

A valid T shape must satisfy the following geometric conditions:

• The horizontal segment has an odd length \(w\) and a minimum length of \(3\).
• The vertical segment has a minimum length \(h\) of \(2\).
• The vertical segment must intersect the horizontal segment exactly at its midpoint. In other words, if the T is defined by its top-left position \((r,c)\) and has horizontal length \(w\) and vertical length \(h\), then the vertical segment is in column \(c+\lfloor w/2 \rfloor\) and spans from row \(r\) to row \(r+h-1\). The horizontal segment is in row \(r\) spanning columns \(c\) to \(c+w-1\).

In addition, a valid T must satisfy these additional constraints:

• \(w \ge a\)
• \(h \ge b\)
• \(w \times h \ge s\)
• \(w+h \ge x\)

Each T shape is uniquely determined by its top-left coordinate \((r,c)\), its horizontal length \(w\), and its vertical length \(h\). The T shape appears in the grid if all the cells in the horizontal segment and the vertical segment are '1'.

The input is a binary matrix of size \(n \times m\) along with the parameters \(a, b, s, x\). You are to count all distinct valid T shapes in the matrix that satisfy the above conditions.

Note: The shared cell between the horizontal and vertical segments is counted in both the horizontal and vertical lengths.

inputFormat

The first line contains six integers: \(n\), \(m\), \(a\), \(b\), \(s\), and \(x\), where \(n\) and \(m\) denote the number of rows and columns of the matrix, and \(a, b, s, x\) are the constraint parameters as described above.

Then follow \(n\) lines, each containing a string of length \(m\) consisting only of the characters '0' and '1', representing the matrix.

outputFormat

Output a single integer — the number of distinct valid T shapes in the given matrix that satisfy the conditions.

sample

3 3 3 2 6 5
111
010
000

1