[USACO26FEB] Swap to Win B

题目描述

农夫约翰有一个他最喜欢的字符串 $t$，长度为 $M$ 个字符。他还有 $N$ 个字符串 $s_1, s_2, \ldots, s_N$，每个长度也都是 $M$ 个字符（$1 \leq N, M \leq 1000$）。

FJ 可以执行以下两种类型的操作：

• FJ 选择任意一个字符串 $s_x$ 和两个下标 $p, q$。然后，他交换 $s_x$ 的第 $p$ 个和第 $q$ 个字符（$1\le x\le N, 1\le p,q\le M$）。
• FJ 选择两个字符串 $s_x$ 和 $s_y$ 以及一个下标 $k$。然后，他交换 $s_x$ 和 $s_y$ 的第 $k$ 个字符（$1\le x,y\le N, 1\le k\le M$）。

他的目标是使 $s_1$ 等于 $t$。请找出任意一系列操作来实现他的目标。由于 FJ 很着急，他总共只有时间执行 $2M$ 次操作。输入保证可以实现 FJ 的目标。

输入格式

第一行包含 $T$（$1\le T\le 10$），表示独立测试用例的数量。每个测试用例按以下格式给出：

第一行包含 $N$ 和 $M$。

第二行包含 $t$。

接下来 $N$ 行，第 $i$ 行包含 $s_i$。

输入保证可以实现 FJ 的目标。所有字符串仅包含小写英文字母（a-z）。

输出格式

每个测试用例的输出格式如下：

第一行输出一个整数 $K$，表示你将执行的操作次数。$K$ 必须是一个非负整数，且不超过 $2M$。

接下来输出 $K$ 行，按顺序表示你将执行的操作。每行应为以下格式之一：

• 1 x p q
• 2 x y k

输入输出样例 #1

输入 #1

3
3 6
banana
nabana
banana
nnbaaa
5 3
abc
def
bca
ghi
jkl
mno
3 5
abcde
abcde
abcde
zzzzz

输出 #1

3
2 1 2 1
1 1 3 5
2 1 2 5
5
1 2 1 3
2 1 2 1
1 2 2 3
2 1 2 2
2 1 2 3
0

说明/提示

根据第一个测试用例的输出，$s$ 的变化过程如下（被交换的字母用大写表示）：

nabana    Babana    baNaBa    banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa    nnbaaa    nnbaaa    nnbaaa

在执行完所有三个操作后，$s_1=t$。

评分标准

• 输入 2-6：$N, M \le 100$
• 输入 7-12：无额外限制。

题目来源：Chongtian Ma

翻译由 DeepSeek 完成