[ICPC2021 Macao R] So I'll Max Out My Constructive Algorithm Skills

**【题目描述】** 宝宝女巫被困在一个 $n$ 行 $n$ 列的迷宫中，其中第 $i$ 行第 $j$ 列的单元格高度为 $h_{i,j}$。要走出迷宫，宝宝必须找到一条路径，该路径穿过每个单元格恰好一次。每次她只能移动到与当前单元格共享边的相邻单元格。但是众所周知，宝宝非常懒，所以每当她爬升（即从高度较低的单元格移动到高度较高的单元格）时，她的幸福值会减少。作为她的帮手，你的任务是找到一条有效的路径，使得沿着路径移动时，宝宝爬升的次数不多于她下降的次数。 更正式地说，你需要找到一个序列 $(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})$，使得： - 对于所有的 $1 \le i \le n^2$，$ 1 \le x_i, y_i \le n$； - 对于所有的 $1 \le i, j \le n^2, i \neq j$，$ (x_i, y_i) \neq (x_j, y_j)$； - 对于所有的 $2 \le i \le n^2$，$|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$； - $\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}$，其中 $[P]$ 当 $P$ 为真时等于 $1$，当为假时等于 $0$。 此外，你发现所有单元格的高度都是 $n^2$ 的排列，所以你只需要输出有效路径中每个单元格的高度。 **【输入格式】** 有多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$（$2 \le n \le 64$），表示迷宫的大小。 接下来的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}$（$1 \le h_{i, j} \le n^2$），其中 $h_{i,j}$ 表示第 $i$ 行第 $j$ 列单元格的高度。保证输入中的所有整数构成 $n^2$ 的排列。 **【输出格式】** 对于每个测试用例，输出一行，包含 $n^2$ 个由空格分隔的整数，表示有效路径中每个单元格的高度。如果有多个有效答案，你可以输出其中任何一个。很容易证明答案总是存在。 请不要在每行的末尾输出多余的空格，否则你的答案可能会被认为不正确！ 翻译来自于：[ChatGPT](https://chatgpt.com/)。

BaoBao the Witch is stuck in a maze with $n$ rows and $n$ columns, where the height of the cell in the $i$-th row and the $j$-th column is $h_{i,j}$. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down. More formally, you need to find a sequence $(x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})$ such that: - For all $1 \le i \le n^2$, $ 1 \le x_i, y_i \le n$; - For all $1 \le i, j \le n^2, i \neq j$, $ (x_i, y_i) \neq (x_j, y_j)$; - For all $2 \le i \le n^2$, $|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$; - $\sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}^{n^2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}$, where $[P]$ equals $1$ when $P$ is true, and equals $0$ when it is false. Additionally, you discover that the heights in all cells are a permutation of $n^2$, so you just need to output the height of each cell in a valid path.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$) indicating the number of test cases. For each test case: The first line contains an integer $n$ ($2 \le n \le 64$) indicating the size of the maze. For the following $n$ lines, the $i$-th line contains $n$ integers $h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}$ ($1 \le h_{i, j} \le n^2$) where $h_{i,j}$ indicates the height of the cell in the $i$-th row and the $j$-th column. It's guaranteed that all integers in the input make up a permutation of $n^2$.

For each test case output one line containing $n^2$ separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It's easy to prove that an answer always exists. Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

1
2
4 3
2 1

4 3 1 2