rt,比赛结束了,终于可以请教大佬了!
思路:一个字母对应多个字母是不合法的,然后统计转换数类似建成图,此外每一棵基环树都会多耗费一次转换,这时如果52个字母都需要转换那么也是不合法的
#include <iostream>
#include <cstring>
using namespace std;
int T;
string a,b;
int len;
int mp[140];
int vis[140];
int vn[140];
int ans;
int use;
bool huan;
int main()
{
cin>>T;
while(T--)
{
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
ans=0;
use=0;
huan=0;
cin>>a>>b;
len=a.length();
a=' '+a;
b=' '+b;
for(int i=1;i<=len;++i)
if(!mp[a[i]])
{
++use;
mp[a[i]]=b[i];
if(a[i]!=b[i]) ++ans;
}
else if(mp[a[i]]!=b[i])
{
ans=-1;
break;
}
if(ans==-1)
{
cout<<-1<<endl;
continue;
}
for(int i='a';i<='z';++i)
{
int tmp=i;
while(true)
{
if(tmp==0 || vis[tmp]) break;
vn[tmp]=1;
if(tmp==mp[tmp]) break;
tmp=mp[tmp];
if(vn[tmp])
{
huan=1;
++ans;
break;
}
}
for(int j=50;j<=130;++j) if(vn[j]) vis[j]=1,vn[j]=0;
}
for(int i='A';i<='Z';++i)
{
int tmp=i;
while(true)
{
if(tmp==0 || vis[tmp]) break;
vn[tmp]=1;
if(tmp==mp[tmp]) break;
tmp=mp[tmp];
if(vn[tmp])
{
huan=1;
++ans;
break;
}
}
for(int j=50;j<=130;++j) if(vn[j]) vis[j]=1,vn[j]=0;
}
if(huan && use==52) ans=-1;
cout<<ans<<endl;
}
return 0;
}