Description

The Guru is on TV! This news is absolutely explosive. As soon as it spreads, the streets instantly become empty (everyone went home to watch TV), shops close, and factories stop. Everyone turns their TV volume to the maximum, and the Guru’s voice echoes through the streets and alleys.

Xiao L hurriedly turns on the TV at home and finds that all channels are broadcasting the Guru’s interview program (-_-bbb). On the screen, the smiling Guru presents a difficult task:

A large diamond with side length $n$ is evenly divided into an $n \times n$ grid made of unit diamonds with 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 whose interiors contain no edges (i.e., the interior is empty).

This task is split into two subproblems. In this subproblem (Diamond A), given the diamond-shaped grid described by slashes and backslashes below, please convert it into an axis-aligned rectangular grid and output the presence of edges as $0/1$ in the specified format. The actual counting of parallelograms is handled in Diamond B.

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: a space, $\verb!/!$, or $\verb!\!$.

• For the first $n$ lines (the upper half of the diamond), the $i$-th line (1-indexed) has exactly $2i$ non-space positions centered in the line. Among these $2i$ positions:

  • Characters at odd positions can only be $\verb!/!$ or a space.
  • Characters at even positions can only be $\verb!\!$ or a space. A space means that the corresponding edge does not exist. All other characters outside these centered $2i$ positions are spaces. These lines describe the upper half of the diamond.

• For the last $n$ lines (the lower half of the diamond), the $i$-th line (1-indexed within the lower half) has exactly $2(n - i + 1)$ non-space positions centered in the line, described in the same way as above, forming the lower half of the diamond.

• It is guaranteed that no edge on the outer boundary of the large diamond is erased.

Output Format

• The first line outputs the integer $n$.

• Then output $2n+1$ lines that describe the edges after converting the diamond grid into an $n \times n$ axis-aligned rectangular grid (think of rotating by $45^\circ$ and scaling). Use $1$ for an existing edge and $0$ for a missing edge. Specifically:

  • Lines $1$ to $n+1$: horizontal edges. Each of these lines contains exactly $n$ characters, each being $0$ or $1$. The $j$-th character on line $i$ (1-indexed) indicates whether the horizontal edge between grid points $(i-1, j-1)$ and $(i-1, j)$ exists.
  • Lines $n+2$ to $2n+1$: vertical edges. Each of these lines contains exactly $n+1$ characters, each being $0$ or $1$. Let $r = i - (n+1)$ for line index $i$ in this range. The $j$-th character on line $i$ indicates whether the vertical edge between grid points $(r-1, j-1)$ and $(r, j-1)$ exists.

4
   /\   
  /\/\  
 /\  /\ 
/  \/  \
\/\/ / /
 \/\  / 
  \ \/  
   \/   

4
1111
11101
1000
10111
1100
10101
0111
11101
1111

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