AdditionalFile5560.zip

#5560. 「POI2026 R1」Rozwiązanie pokojowe

标签: 传统 | 时间限制: 10000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Rozwiązanie pokojowe

有一块 $n \times n$ 的国际象棋棋盘，行和列均从 $1$ 到 $n\times n$ 编号。 棋盘上放置了 $k$ 个国王，编号分别为 $1$ 到 $k$。与标准国际象棋规则相同，每个国王可以向八个方向移动一格（即相邻的任意格子，包括斜向）。

当前国王们对初始位置不太满意，每位国王都选定了一个目标位置（可能与起始位置相同）。 他们希望通过一系列移动，从初始布局变换到目标布局。

移动规则如下：

• 每次操作选择一个国王，将其移动到与当前格子相邻的格子（八方向均可，不能原地不动）。
• 在整个移动过程中的任意时刻，任意两个国王都不能处于相邻格子（即不能相互攻击）。

初始布局和目标布局均满足任意两个国王不相邻的条件。

请你判断是否可能完成这种变换。如果可以，请输出一种合法的移动序列；否则输出不可能。

输入格式

第一行两个整数 $n, k$ $(1 \leq n \leq 100,1 \leq k \leq 2500)$，表示棋盘大小和国王数量。

接下来 $n$ 行，每行 $n$ 个整数，描述初始布局：若格子 $(i,j)$ 上的数 $a_{i,j} > 0$，则表示编号为 $a_{i,j}$ 的国王；$0$ 表示空位。

再接下来 $n$ 行，以相同格式描述目标布局 $b_{i,j}$。

保证 $1$ 到 $k$ 的每个编号在初始和目标布局中恰好出现一次。初始与目标布局中任意两个国王都不相邻（八方向）。

输出格式

如果不可能，输出一行 NIE。

如果可能，第一行输出 TAK。

第二行输出一个整数 $m$ $(0 \leq m \leq 5 \times 10^6)$，表示你给出的移动序列长度。
（可证明若存在解，则一定存在长度不超过此限制的解）

接下来 $m$ 行，每行三个整数 $c\ i\ j$，表示将编号为 $c$ 的国王移动到第 $i$ 行第 $j$ 列的格子。要求 $(i,j)$ 必须与该国王当前所在格子相邻（八方向，不能原地）。移动后，该格子不能与任何其他国王相邻（即整个过程始终保持国王互不攻击）。

若有多种方案，输出任意一种即可。

只要第一行判断正确（TAK/NIE），即使后面移动序列缺失或错误，仍可得到该测试点 $20\%$ 的分数。

样例 1

输入

4 3
1 0 2 0
0 0 0 0
0 3 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0
0 2 0 3

输出

TAK
13
3 3 1
2 2 3
3 4 2
3 4 3
3 4 4
2 3 2
1 1 2
1 1 3
2 3 1
3 3 3
3 4 4
2 4 2
1 2 3

样例 2

输入

5 8
1 0 2 0 3
0 0 0 0 0
4 0 5 0 6
0 0 0 0 0
7 0 8 0 0
2 0 3 0 0
0 0 0 0 6
4 0 1 0 0
0 0 0 0 8
7 0 5 0 0

输出

NIE

附加样例

1. $n=100, k=50$，初始时奇数对角线上放国王 $1\sim 50$，目标是逆序放到同一对角线

数据范围与提示

详细子任务附加限制及分值如下表所示。