Description

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.

Input Format

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 Format

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

4
1111
11101
1000
10111
1100
10101
0111
11101
1111

3

Hint

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