P2363 Ma Nong

After watching a warhorse review, two brothers from the grasslands decide to become super "ma nong" (horse ranchers), specializing in raising warhorses. They return to the grassland and divide the area suitable for horse ranching into $N \times N$ unit square cells, then conduct a field survey to summarize the profit obtainable from raising horses on each unit area. Next, they will plan their respective ranches. First, both ranches must each be a rectangular region. Also, to facilitate mutual care and prevent horses from straying, the two rectangular ranches must be adjacent and have exactly one common point (i.e., they touch at a single point). Finally, the two competitive brothers want the total profits of the two ranches to be equal, so as not to hurt their relationship. Now, they ask you, the designer, to design their ranches: how many valid design plans are there?

The first line contains an integer $N$, indicating that the entire grassland is of size $N \times N$. The next $N$ lines each contain $N$ integers $A_{i,j}$, representing the profit of the unit grassland at row $i$, column $j$. (Note: profits may be negative; raising horses is not guaranteed to be profitable, and accidents such as illness or death may occur.)

Output the number of grassland allocation plans that meet the brothers’ requirements.

For all testdata, $1 \leq N \leq 50$. Translated by ChatGPT 5