P6600 "EZEC-2" Letter

You are given a $01$ matrix. We want you to find a “letter T” made of consecutive $1$'s inside it.

A “letter T” consists of one horizontal stroke and one vertical stroke, and the vertical stroke must be below the horizontal stroke (you may use the English letter `T` to help understand). In this problem, we define the “horizontal stroke” as the horizontal line segment forming the “letter T”, and the “vertical stroke” as the vertical line segment forming the “letter T”. Note that the overlapping part of the horizontal and vertical strokes is counted in both the horizontal length and the vertical length. **For a valid “letter T”, the length of the horizontal stroke must be odd, and the vertical stroke must intersect the horizontal stroke at its midpoint. The minimum horizontal length is $3$, and the minimum vertical length is $2$.** For example: $$ \begin{array}{ccc} 0\color{Red}111\color{black}1\\ 00\color{Red}1\color{black}01 \end{array} $$ There is **only** one valid “letter T” (the red part). Now you are given a $n \times m$ $01$ matrix. Please find, among all **valid** “letter T”s in this matrix, how many “letter T”s **satisfy the following conditions**. Suppose a valid “letter T” has horizontal length $w$ and vertical length $h$. Then: - $w\ge a$ - $h\ge b$ - $w\times h \ge s$ - $w+h\ge x$ Two “letter T”s are considered different if their **horizontal length**, **vertical length**, or the **coordinates of the top-left corner** are different.

The first line contains two integers $n,m$, meaning the given $01$ matrix has $n$ rows and $m$ columns. The second line contains four integers $a,b,s,x$. The next $n$ lines each contain $m$ numbers, which can only be $0$ or $1$, representing the given matrix.

Output one integer, the number of **valid** “letter T”s that **satisfy the conditions**.

**[Sample Explanation #1]** $$ \begin{array}{ccc} \color{Red}11111\qquad11111\\01\color{Red}1\color{black}10\qquad01\color{Red}1\color{black}10\\ 11\color{Red}1\color{black}11\qquad11\color{Red}1\color{black}11\\ 01\color{Red}1\color{black}10\qquad01\color{Red}1\color{black}10\\ 11111\qquad11\color{Red}1\color{black}11\\\\ The\ 1st\qquad The\ 2nd \end{array} $$ Other than the two “letter T”s above, there are no other valid “letter T”s that satisfy the conditions, so the output is $2$. **[Constraints]** | Test Point ID | $n,m\le$ | $a,b\le$ | $s\le$ | $x\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1 \sim 4$ | $100$ | $100$ |$10^4$|$200$| | $5 \sim 8$ | $500$ | $500$ |$2.5\times 10^5$|$10^4$| | $9,10$ | $3\times 10^3$ | $0$ |$0$|$0$| | $11\sim 13$ | $3\times 10^3$ |$3\times 10^3$|$0$|$6\times 10^3$| | $14\sim 16$ | $3\times 10^3$ |$3\times 10^3$|$9\times 10^6$|$0$| | $17\sim 20$ | $3\times 10^3$ |$3\times 10^3$|$9\times 10^6$|$6\times 10^3$| For $100\%$ of the testdata, $1 \le n,m \le 3\times 10^3$, $0 \le a,b \le 3\times10^3$, $0 \le s \le 9\times10^6$, $\space0 \le x \le 6\times10^3$. Translated by ChatGPT 5