AT_ahc062_a [AHC062A] King's Tour

AtCoder 王国は $ N \times N $ のグリッド状の区画に区切られており、各区画にはそれぞれ異なる人数の国民が住んでいる。 国王の高橋君は、国民からの好感度を上げるため、縦・横・斜めに隣接する区画を辿りながら、すべての区画を一度ずつ訪問するツアーを計画している。 ツアーは日を追うごとに盛り上がっていくので、後の日に訪れた区画ほど、住人の高橋君への好感度が高くなる。 高橋君が得る好感度の総和がなるべく大きくなるようなツアーを計画してほしい。

有一个王国被划分为 $N \times N$ 的区域网格。左上角的区域被标记为 $(0,0)$，向下移动 $i$ 个区域、向右移动 $j$ 个区域所到达的区域为 $(i,j)$。区域 $(i,j)$ 有 $A_{i,j}$ 名居民。 现在考虑一条旅行路线，在 $N^2$ 天内恰好访问每个区域一次，从第 $0$ 天到第 $N^2-1$ 天。第 $k$ 天访问的区域为 $(i_k, j_k)$。 要求连续两天所访问的区域必须为**相邻**区域，允许上下、左右或对角线相邻。更精确地说，对于每个 $k=0,1,\dots,N^2-2$，需要满足 \[ \max\bigl(|i_k-i_{k+1}|,~ |j_k-j_{k+1}|\bigr)=1 \] 起点和终点可以任取。 第 $k$ 天到达的区域，每名居民会贡献 $k$ 点好感。Takahashi 获得的总好感值为 \[ \sum_{k=0}^{N^2-1} k\cdot A_{i_k, j_k} \] 请你找出一条访问顺序，使 Takahashi 获得的总好感值尽可能大。

输入以如下格式从标准输入给出： > $N$ > $A_{0,0}$ $A_{0,1}$ $\cdots$ $A_{0,N-1}$ > $\vdots$ > $A_{N-1,0}$ $A_{N-1,1}$ $\cdots$ $A_{N-1,N-1}$ - 所有测试用例中 $N=200$。 - $A_{i,j}$（区域 $(i,j)$ 的居民数）是满足 $1\leq A_{i,j}\leq N^2$ 的整数。

令第 $k$ 天访问的区域为 $(i_k, j_k)$。请输出如下格式到标准输出： > $i_0$ $j_0$ > $\vdots$ > $i_{N^2-1}$ $j_{N^2-1}$ 你的输出必须满足以下所有条件： - 对每个 $k=0,1,\cdots,N^2-1$，$i_k$ 和 $j_k$ 是 $0$ 到 $N-1$ 之间的整数（含端点）。 - 所有 $(i_k, j_k)$ 在 $k=0,1,\cdots,N^2-1$ 时均不相同。 - 对每个 $k=0,1,\cdots,N^2-2$，都有 $ \max(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|)=1 $。

### 评分方式 设 $V$ 为 Takahashi 获得的总好感值，则该测试点的分数为 \[ \mathrm{round}\left(\frac{V}{N^2}\right) \] 共有 $100$ 个测试点，提交的总分为各测试点得分之和。如果输出非法或部分测试点超时，该提交整体将按 WA 或 TLE 判定，分数为零。比赛期间获得的最高分即为最终排名，赛后不会再有系统测试。如果多名参赛者得分相同，则排名相同，与提交时间无关。 ### 输入生成方式 - 所有测试点均有 $N=200$。 - $1$ 到 $N^2$ 的整数被均匀随机洗牌，依次赋给 $A_{0,0}, A_{0,1},\cdots,A_{0,N-1}, A_{1,0},\cdots,A_{N-1,N-1}$。 ### 工具（输入生成器和可视化工具） - [网页版](https://img.atcoder.jp/ahc062/u5OpcTjC.html?lang=ja)：比本地版更强大，支持动画。 - [本地版](https://img.atcoder.jp/ahc062/u5OpcTjC.zip)：需要配置 [Rust 语言](https://www.rust-lang.org/) 环境。 - [Windows 预编译版](https://img.atcoder.jp/ahc062/u5OpcTjC_windows.zip)：如果不熟悉 Rust 环境可优先考虑。 请注意，比赛期间禁止共享可视化结果、讨论解法或思路。 由 ChatGPT 5 翻译