P14649 [POI 2025/2026 #1] 互不侵犯 / Rozwiązanie pokojowe

滥用评测者将被封号。

给定一个大小为 $n \times n$ 的国际象棋棋盘，行和列用从 1 到 $n$ 的整数编号。在棋盘上放置了 $k$ 个国王，用从 1 到 $k$ 的整数编号。与标准国际象棋规则相同，每个国王都可以向八个方向移动，也就是说，在一步之内它可以移动到任意一个相邻的格子：即与当前所占格子共享边或顶点的格子。 国王们对当前的初始摆放不太满意，每个国王都为自己选定了一个想要到达的目标格子(可能与它的初始格子相同)。他们想通过一系列移动，把自己的位置从初始摆放变为目标摆放。每一步移动是：选择某个国王，把它从当前所在的格子移动到一个相邻的格子。整个过程中在任何时刻，都不能出现某一对国王占据相邻格子的情况。 你的任务是帮助这些国王，给出这样一系列移动，或者指出这是不可能的。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100, 1 \le k \le 2500$），分别表示棋盘的大小和国王的数量。接下来的 $n$ 行描述初始摆放。 第 $i$ 行的描述（$1 \le i \le n$）由 $n$ 个整数组成；其中第 $j$ 个数 $a_{i,j}$ 表示：在第 $i$ 行第 $j$ 列的格子上，有编号为 $a_{i,j} > 0$ 的国王；或者如果 $a_{i,j} = 0$，则该格子为空。 接下来的另 $n$ 行以同样的方式给出目标摆放(即第 $i$ 行包含 $n$ 个数 $b_{i,j}$，其中 $b_{i,j}$ 表示国王的编号，或者为 0 表示该格子为空)。 对于每个 $i, j$（$1 \le i, j \le n$），都有 $0 \le a_{i,j}, b_{i,j} \le k$，并且从 1 到 $k$ 的每个整数在初始摆放 $a$ 中恰好出现一次，在目标摆放 $b$ 中也恰好出现一次。 在初始摆放和目标摆放中，任意两个国王都不占据相邻的格子。

你的程序应在第一行输出单词 TAK，如果存在所需的移动序列；否则输出单词 NIE。 如果答案是 TAK，则第二行应输出一个整数 $m$（$0 \le m \le 5 \cdot 10^6$），表示你的方案中的移动步数。可以证明，如果所需的移动序列存在，那么存在一个满足上述长度限制的序列。 在接下来的 $m$ 行中，你需要输出依次进行的每一步移动的描述。 每一行应包含三个整数 $c, i, j$，表示编号为 $c$ 的国王应移动到第 $i$ 行第 $j$ 列的格子上。该格子必须与该国王当前所在格子相邻（特别地，不能是它当前所在的格子本身），并且不能与任何其他国王所占据的格子相邻。

### 大样例 可以在附件中获得大样例。 样例 $\texttt{0a}$ 和 $\texttt{0b}$ 是题面中展示的样例。此外 - $\texttt{0c}$： - $n = 100, k = 50$； - $a_{i,j} = (i+1)/2$ 如果 $i=j$ 且 $i$ 为奇数，否则 $a_{i,j} = 0$； - $b_{i,j} = 51 - (i+1)/2$ 如果 $i=j$ 且 $i$ 为奇数，否则 $b_{i,j} = 0$。 ### 子任务 本题采用捆绑测试。 对于每个子任务，在该子任务中价值一半分数的测试里 $n$ 为奇数，在价值另一半分数的测试里 $n$ 为偶数。 在洛谷上评测时，我们将子任务 $2i$（$1\le i\le 4$）设置为子任务 $i$ 中 $n$ 为偶数的测试点；子任务 $(2i-1)$ 类似。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | $1$ | $n \le 5$ | $18$ | | $2$ | $2k \le n$ | $16$ | | $3$ | $n \le 40$ | $38$ | | $4$ | 无额外限制 | $28$ | 如果你的答案只有第一行是正确的，你的解在该测试上将获得 $20\%$ 的分数。为了得到这部分分数，你不必输出后续各行。