题目标题都不会读，我太蕈了
A6n6d6y6
·
·
题解
题意
概括了一下，将就着看。
有一幅 n\times m 的画，每个像素上有一个颜色，有三种操作：
-
选择一个 2\times2 的区域，将其像素顺时针旋转。
-
交换相邻的两个像素。
-
对于一个 h_i\times w_i 的区域，替换成配方列表中的另一个画面。
现在给定你初始的画和 k 种配方，构造一个方案，在使用不大于 400 次替换操作，且总步数在 4\times10^5 步内使其变为另一幅给定的画。
## 思路
不拿发现旋转操作可以用 $O(1)$ 次原地交换解决，所以先不考虑这种操作，除非上界卡得很死。
然后发现正着做操作和状态非常的多。此时考虑离线下来，时光倒流（本人昨天考试才碰到了这个 trick），从最终画面倒着考虑。
那么交换操作显然在新意义下不变。
于是替换操作就变成了每次找到一个配方列表的画面，然后使用这个配方，然后这些字符的取值我们就不关心了（不管原来是什么，总之被覆盖后就是对应的颜色），可以理解为变成了通配符 `*`。
综上，每次枚举每个配方，判断字符数量够不够使用这个配方（注意通配符也要算进去），然后：
- 如果通配符数量不能增加，也就是全用通配符进行的替换，那么这个操作显然无意义。
- 否则找一个位置，把对应的字符挪过去，拼成那个配方，随后将其全部替换成通配符 `*`。
不妨将初始局面也看成一个配方，每次判断初始局面能不能被使用。
最后别忘了把操作序列倒序输出。
然后这道题就成小模拟了，稍微用一点时间就写完了。
## 分析
对于我们上面的操作，分析一下是否符合题目要求的上界。
由于每次都能将至少一个字符转化成通配符，所以只会使用 $O(nm)$ 次配方，而把每个字符移动到我们想要的位置需要 $O(n+m)$ 步，每个字符只会被尝试移动 $O(k)$ 次。
所以只会使用 $O(nm)\le400$ 次替换操作，符合题意。
所以只会使用 $O(nmk(n+m))\le4\times 10^5$ 次替换操作，符合题意。
所以你会发现前面提到的“找一个位置”根本不用可以特殊考虑，实际代码中直接无脑找的左上角。同时这个“旋转操作”十分没用，当作没有就行了。
由于 $n,m,k,|\Sigma|$ 都很小，就不分析总时间复杂度了，随便实现都应该不会 T。
## 代码
代码难度并不高，感觉似乎没有黑？
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+10,maxm=4e5+10;
char c[maxn][maxn][maxn],b[maxn][maxn],(&a)[maxn][maxn]=c[0];
int h[maxm],w[maxm],vis[maxn][maxn],&n=h[0],&m=w[0],k;
struct opt{int op,x,y;}ans[maxm];int cnt[128],tot;
int check(int k){
memset(cnt,0,sizeof cnt);
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cnt[b[i][j]]++;
for(int i=1;i<=h[k];i++){
for(int j=1;j<=w[k];j++){
if(cnt[c[k][i][j]])cnt[c[k][i][j]]--,res++;
else if(cnt['*'])cnt['*']--;
else return -1;
}
}
return res;
}
void solve(int k){
memset(vis,0,sizeof vis);
for(int i=1;i<=h[k];i++){
for(int j=1;j<=w[k];j++){
int x=0,y=0;
for(int l=1;l<=n;l++){
if(x||y)break;
for(int r=1;r<=m;r++)
if(!vis[l][r]&&b[l][r]==c[k][i][j]){x=l,y=r;break;}
}
for(int l=1;l<=n;l++){
if(x||y)break;
for(int r=1;r<=m;r++)
if(!vis[l][r]&&b[l][r]=='*'){x=l,y=r;break;}
}
while(x<i)swap(b[x][y],b[x+1][y]),ans[++tot]={-3,x++,y};
while(y<j)swap(b[x][y],b[x][y+1]),ans[++tot]={-1,x,y++};
while(x>i)swap(b[x][y],b[x-1][y]),ans[++tot]={-4,x--,y};
while(y>j)swap(b[x][y],b[x][y-1]),ans[++tot]={-2,x,y--};
vis[i][j]=1;
}
}
for(int i=1;i<=h[k];i++)
for(int j=1;j<=w[k];j++)
b[i][j]='*';
if(k)ans[++tot]={k,1,1};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>b[i][j];
for(int i=1;i<=k;i++){
cin>>h[i]>>w[i];
for(int j=1;j<=h[i];j++)
for(int l=1;l<=w[i];l++)
cin>>c[i][j][l];
}
while(!~check(0)){
bool f=1;
for(int i=1;i<=k;i++)
if(check(i)>0)f=0,solve(i);
if(f){cout<<-1;return 0;}
}
solve(0);
cout<<tot<<'\n';
for(int i=tot;i>=1;i--){
auto [op,x,y]=ans[i];
cout<<op<<' '<<x<<' '<<y<<'\n';
}
return 0;
}
```