P10612 [BalticOI 2001] Box of Mirrors

The mathematician Andris has a small box whose bottom is an $n \times m$ grid. Each cell can contain a mirror oriented at $45$ degrees. On the boundary of the box, at both ends of every row and every column, there are some holes. Light can enter the box through these holes and can also leave through them.   As shown above, a beam of light entering the box from hole $2$ is reflected twice and then leaves from hole $7$. Andris wants you to design a box so that the beam entering from each hole will leave from a specified hole. For example, if he wants the beams entering from the $10$ holes to leave from holes $9, 7, 10, 8, 6, 5, 2, 4, 1, 3$ respectively, then the box shown above also satisfies the requirement. Note that the holes are numbered from $1$ to $2 \times (n+m)$ as shown in the figures.

The first line contains two integers $n, m$, representing the size of the box. In the next $2 \times (n+m)$ lines, the $(i+1)$-th line contains an integer $a_i$, meaning that the beam entering from hole $i$ must leave from hole $a_i$.

Output an $n \times m$ matrix. For each position, output $0$ to indicate no mirror is placed, and $1$ to indicate a mirror is placed. The output must satisfy the given requirements. The testdata guarantees that a solution always exists.

For $100\%$ of the testdata, $1 \leq n, m \leq 100$, and $1 \leq a_i \leq 2 \times (n+m)$. Translated by ChatGPT 5