这是一篇用 set 的题解。

先考虑 $N,M \le 100$，对于 $t$ 的每个位置，我们暴力枚举所有字符串 $s_i$ 的所有位置（$s_1$ 的已经匹配好了字符的除外），寻找 $t$ 需要的字符的出现位置，并先进行第 $1$ 种操作再进行第 $2$ 种操作，时间复杂度 $O(Tnm^2)$。

然后分析这样做慢在哪里，对于每种字符，即使需要量很少，我们也会对所有位置都要遍历一遍，这显然不优。因此，对于每种字符，我们只记录这种字符出现在哪些位置，并且这种字符在 $t$ 中需要几个，我们就记录几个位置（或直接规定最多记录 $M$ 个位置）；对于每次匹配操作，我们只在记录的位置进行遍历，并在交换时将对应位置交换，最后将移到 $s_1$ 的那个已经匹配好了字符标记为不可以再次使用即可，时间复杂度 $O(Tm(n+m))$，可以通过。

但是由于赛时直接上 set 了而且没调出来，所以讲一下 set 做法：由于上述操作用到的只有在序列上寻找某个值、加入某个数、删除某个数的操作，我们将原来记录每种字符出现位置用 set 维护即可。注意交换时可以先删除数再加入数（或分类讨论等做法），以避免交换操作交换同一个（或同一种）字符造成原来不应该删除的数被删了的问题。由于 set 很慢，这里可以加上剪枝（上文中的“这种字符在 $t$ 中需要几个，我们就记录几个位置”），时间复杂度 $O(Tm(n+\log m))$（加剪枝以后的），set 部分常数巨大。

提交记录 :::info[代码]

#include<cstdio>
#include<set>
using namespace std;
const int N=1010;
struct node {
	int x,y;
	bool operator <(const node &n1) const & {
		if(x==n1.x) return y<n1.y;
		return x<n1.x;
	}
};
set<node> st[26];
int T,n,m,cnt[26];
char t[N],s[N][N];
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		scanf("%s",&t[1]);
		for(int i=1;i<=m;i++) ++cnt[t[i]-'a'];
		for(int i=1;i<=n;i++) {
			scanf("%s",&s[i][1]);
			for(int j=1;j<=m;j++) {
				//这个判断加了最大点 25ms，不加最大点 1.6s 多并会导致时间复杂度退化
				if(cnt[s[i][j]-'a']) {
					st[s[i][j]-'a'].insert({i,j});
					--cnt[s[i][j]-'a'];
				}
			}
		}
		printf("%d\n",m<<1);
		for(int i=1;i<=m;i++) {
			int x=st[t[i]-'a'].begin()->x,y=st[t[i]-'a'].begin()->y;
			printf("1 %d %d %d\n2 1 %d %d\n",x,i,y,x,i);
			st[s[x][y]-'a'].erase({x,y});
			st[s[x][y]-'a'].insert({x,i});
			st[s[x][i]-'a'].erase({x,i});
			st[s[x][i]-'a'].insert({x,y});
			swap(s[x][y],s[x][i]);
			st[s[x][i]-'a'].erase({x,i});
			st[s[x][i]-'a'].insert({1,i});
			st[s[1][i]-'a'].erase({1,i});
			st[s[1][i]-'a'].insert({x,i});
			swap(s[x][i],s[1][i]);
			st[s[1][i]-'a'].erase({1,i});
		}
		for(int i=0;i<26;i++) st[i].clear();
	}
	return 0;
}
/*
2
2 3
aba
dab
cac
2 7
abcdeee
bcdcbcd
eaeaexx
*/

:::