CF995A Tesla

Allen 梦想有一天能拥有一支庞大的电动车队，这正是未来的汽车！他知道这会让他的地位大大提升。当 Allen 规划着他将拥有的各种类型的汽车以及如何安排它们时，他意识到自己遇到了一个问题。 Allen 未来的停车场可以表示为一个 $4$ 行 $n$ 列（$n \le 50$）的矩形空间，每个空间每次最多只能停放一辆车。他设想在这个网格中有 $k$ 辆车（$k \le 2n$），所有的车最初都停在第 $2$ 行和第 $3$ 行。每辆车都有一个指定的停车位，位于第 $1$ 行或第 $4$ 行。Allen 必须将所有车辆停到对应的指定位置。 然而，由于 Allen 绝不会把自己的车交给别人，每次只能移动一辆车。他可以将一辆车从当前位置向四个正方向中的任意一个方向移动到相邻的空位。此外，只有当某辆车正好到达它指定的停车位时，才能将其移动到第 $1$ 行或第 $4$ 行的空间。 Allen 知道自己将会非常忙碌，在他意识到移动汽车不值得花费时间之前，最多只能移动 $20000$ 次。请你帮助 Allen 判断他是否应该自己停车，或者把这件事交给别人。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \le n \le 50$，$1 \le k \le 2n$），分别表示列数和汽车数量。 接下来的四行每行包含 $n$ 个整数，范围在 $0$ 到 $k$ 之间，表示停车场的初始状态。行号从上到下为 $1$ 到 $4$，列号从左到右为 $1$ 到 $n$。 在第一行和最后一行中，整数 $1 \le x \le k$ 表示分配给第 $x$ 号车的停车位（只有该车可以停到这个位置），整数 $0$ 表示空位（不能将任何车停到这里）。 在第二行和第三行中，整数 $1 \le x \le k$ 表示第 $x$ 号车的初始位置，整数 $0$ 表示空位（任何车都可以移动到这里）。 每个 $x$（$1 \le x \le k$）在第二行和第三行中各出现一次，在第一行和第四行中也各出现一次。

如果存在一种移动方案，能在不超过 $20000$ 步内将所有车辆停到指定位置，输出 $m$，即移动次数。接下来的 $m$ 行，每行输出一次移动，格式为 $i\ r\ c$，表示 Allen 将第 $i$ 号车移动到第 $r$ 行第 $c$ 列的相邻空位。 如果无法在 $20000$ 步内完成任务，输出一行 $-1$。

在第一个样例测试中，所有车辆都停在了各自停车位前面，除了第 $5$ 号车，它停在了相邻停车位的前面。示例展示了最短的移动序列，但只要移动次数不超过 $20000$ 的方案都可以被接受。 在第二个样例测试中，只有一列，车辆顺序错误，因此无法移动，任务不可能完成。 由 ChatGPT 4.1 翻译