4221. 洗牌

原题链接：https://www.acwing.com/problem/content/description/4224/

#include<bits/stdc++.h>
using namespace std;

string a,b,c;
unordered_map<string,int> dist;
int n;

string sff(string a,string b)
{
    string c;
    for(int i=0;i<n;i++)
    {
        c+=a[i];
        c+=b[i];
    }
    return c;
}

void bfs()
{
    queue<string> q;
    string x=sff(b,a);
    dist[x]=1;
    q.push(x);
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t==c) return;
        string a,b;
        for(int i=0;i<n;i++) a+=t[i],b+=t[i+n];
        string c=sff(b,a);
        if(!dist.count(c)){
            dist[c]=dist[t]+1;
            q.push(c);
        }
    }
}
int main()
{
    int tt;
    scanf("%d",&tt);
    for(int i=1;i<=tt;i++)
    {
        dist.clear();
        cin>>n;
        cin>>a>>b>>c;
        bfs();
        if(!dist.count(c)) dist[c]=-1;
        printf("%d %d\n",i,dist[c]);
    }
}