P1741 Diamond A&B(2)

Because this problem is difficult, it has been split into two problems, diamond A and diamond B. This problem is Diamond B.

Jiaozhu went on TV! This is absolutely explosive news. As soon as it spread, the streets instantly emptied (everyone went home to watch TV), shops closed, and factories halted. Everyone turned their TV volume to the maximum, and Jiaozhu’s voice echoed through every street and alley. Xiao L hurriedly turned on the TV at home and found that every channel was broadcasting Jiaozhu’s interview program (-_-bbb). On the screen, Jiaozhu smiled and posed a challenge: A large diamond of side length $n$ is uniformly divided into an $n \times n$ grid of small diamonds of side length $1$. However, some edges in the grid have been erased. Xiao L wants to know how many parallelograms are inside the large diamond such that the interior of each parallelogram contains no edges (i.e., the parallelogram’s interior is empty). Jiaozhu said that whoever writes the program should, if using Mobile, send the program to xxxx; if using Unicom, send the program to xxxx… If you answer correctly, you will have a chance to enter a lottery. The grand prize is an Orz Jiaozhu T-Shirt with Jiaozhu’s signature! This prize is too tempting. Thus you need to write a program to solve this problem.

The first line contains a positive integer $n$, the side length of the large diamond. The next $2n$ lines each contain $2n$ characters. Each character is one of: space, \verb!/!, \verb!\!. For the first $n$ lines (the upper half of the diamond), in line $i$ there is a centered block of $2i$ characters. Among these $2i$ characters, characters in odd positions can only be \verb!/! or a space, and characters in even positions can only be \verb!\! or a space. A space means that such an edge does not exist. All other characters in the row (outside the centered block) are spaces, describing the upper half of the large diamond. For the last $n$ lines (the lower half of the diamond), in the $i$-th line (counting from the top of the lower half, 1-indexed) there is a centered block of $2(n - i + 1)$ characters, described similarly to the upper half, describing the lower half of the diamond. The input guarantees that no edge on the outline of the large diamond is erased.

Output a single integer: the number of parallelograms that satisfy the requirement.

### Constraints - For $20\%$ of the testdata, $n \le 10$. - For $40\%$ of the testdata, $n \le 60$. - For $60\%$ of the testdata, $n \le 200$. - For $100\%$ of the testdata, $n \le 888$. Translated by ChatGPT 5