P3568 [POI 2014] WAZ-Snake

# Description A snake fills a $3 \times n$ board completely. The snake is divided into segments numbered from $1$ to $3n$. Consecutive segments (i.e., $k$ and $k+1$) must occupy squares that share an edge. Some segment numbers on the board are erased. Can you reconstruct the snake? Constraints: $1 \le n \le 1000$.

A snake fills a $3 \times n$ board completely. The snake is divided into segments numbered from $1$ to $3n$. Consecutive segments (i.e., $k$ and $k+1$) must occupy squares that share an edge. Some segment numbers on the board are erased. Can you reconstruct the snake? Constraints: $1 \le n \le 1000$. # Description

The first line contains an integer $n$ ($1 \le n \le 1000$), the length of the board. The next three lines describe the board. The $i$-th of these lines contains $n$ integers $a_{i j}$ ($0 \le a_{i j} \le 3n$) for $1 \le j \le n$. If $a_{i j} > 0$, then $a_{i j}$ is the number of the snake’s segment occupying the $j$-th square of the $i$-th row. If $a_{i j} = 0$, then the number on this square is unknown. It is guaranteed that there is at least one valid reconstruction.

Print three lines. The $i$-th line should contain $n$ positive integers $b_{i j}$ ($1 \le j \le n$). All numbers $b_{i j}$ together must form a permutation of $1, 2, \dots, 3n$. For every $(i, j)$ with $a_{i j} > 0$, it must hold that $b_{i j} = a_{i j}$. Moreover, for every $k$ from $1$ to $3n-1$, the squares containing $k$ and $k+1$ must share an edge. If multiple solutions exist, output any of them.

Translated by ChatGPT 5