No.3338 Whole Reverse Contradiction
Problem Statement
There is a grid with $N$ rows and $N$ columns. Let $(i,\ j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
Each cell contains an integer; the written integers are between $1$ and $N^2$, inclusive, and are all distinct.
There are the following $2$ types of operations.
- Operation $1$: Choose $1$ row and reverse that row left to right.
- Operation $2$: Choose $1$ column and reverse that column upside down.
However, as in operation $1$ $\rightarrow$ operation $2$ $\rightarrow$ operation $1$ $\rightarrow$ operation $2$ $\rightarrow$ $\cdots$, throughout the entire sequence of operations, you must perform operation $1$ at odd-numbered steps and operation $2$ at even-numbered steps.
Given that the number initially written in cell $(i,\ j)$ is $A_{i,j}$, is it possible to make the number written in cell $(i,\ j)$ equal to $(i - 1) \times N + j$ after the operations are completed?
If it is possible, find one example of such a sequence of operations; if it is impossible, report so.
You are given $T$ test cases; solve each of them.
Constraints
- All input values are integers.
- $1 \leq T \leq 10^4$
- $2 \leq N \leq 300$
- $1 \leq A_{i,j} \leq N^2$
- $A_{i_1, j_1} \neq A_{i_2, j_2}\ ((i_1,\ j_1) \neq (i_2,\ j_2))$
- The sum of $N^2$ in $1$ input file does not exceed $9 \times 10^4$.
Input
The input is given from Standard Input in the following format, where $case_i$ denotes the $i$-th case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$N$
$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \cdots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$
Output
For each case, if no sequence of operations satisfying the conditions exists, output -1; if one exists, output one example of it in the following format.
$K$ $B_1\ B_2\ \cdots\ B_K$
Here, $K$ is the total number of operations. When $i$ is odd, $B_i$ represents which row from the top is chosen in the $i$-th operation, and when $i$ is even, $B_i$ represents which column from the left is chosen in the $i$-th operation.
Print a newline at the end of the output for each case.
Sample
Sample 1
Input
2 4 1 2 15 4 8 11 6 5 9 10 7 12 13 14 3 16 2 1 2 3 4
Output
2 2 3 0
For the $1$st test case, if you reverse the $2$nd row from the top and the $3$rd column from the left in this order, the numbers written in the grid change as shown in the figure below, and the number written in the cell in the $i$-th row from the top and the $j$-th column from the left becomes $(i - 1) \times N + j$, so this is a correct answer.
For the $2$nd test case, the condition is satisfied from the start, so no operations need to be performed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
cn_449