If the grid has an odd number of Ys, the answer is clearly \(0\). Below, assume that this number is even, and let \(y\) be half this value.

If you set up fences to satisfy the condition, there must be exactly \(y\) blocks since each block has exactly two Y squares. Thus, if we let \(h\) and \(w\) be the number of fences between rows and between columns, respectively, we have \((h+1)(w+1) = y\). This means the value of \(h + 1\) can only be divisors of \(y\). Let us try all of these values that satisfy the following:

\[0 \le h < H,\ \ 0 \le w = \frac{y}{h+1} - 1 < W.\]

For a fixed pair \((h, w)\) satisfying the above, there is essentially a single way to set up fences. This is because:

• if just the \(h\) fences between rows are set up, each block must have exactly \(2(w+1)\) Ys, and
• if just the \(w\) fences between columns are set up, each block must have exactly \(2(h+1)\) Ys.

However, if there is a row or column consisting of just X, you may set up a fence on either side of that row or column. The number of ways to set up fences is the product of these degrees of freedom, or \(0\).

Let us pre-compute the two-dimensional cumulative sums of the number of Ys from the top-left corner, naively in \(\mathrm{O}(HW)\) time. Then, we can find the positions to install fences (and the degree of freedom) to satisfy the necessary conditions for rows and columns in \(\mathrm{O}(H + W)\) time. Additionally, if there are positions to install fences to satisfy both of those conditions, we can check whether the original condition (two Ys in each block) is satisfied in \(\mathrm{O}(y)\) time.

The total complexity is \(\mathrm{O}(HW + k(H + W + y))\), where \(k\) is the number of pairs \((h, w)\) to try. Under the constraints, we have \(k \le 80,\ ky \le 6.1 \times 10^7\) (try all possible \(y\)’s to see this), and the constant factor is not large, so it runs in time.

Sample implementation