ACM算法竞赛试题——宇宙魔方

Question

题目描述:
邪神洛基偷走了宇宙魔方，美国队长要夺回它。他发现宇宙魔方被锁在了一个特制的密码箱中，密码箱上目前显示着一串文字（字符串a）。钢铁侠帮助美国队长破解了密码箱的操作方式：每次可以按照规则把一个字母转换为另一个字母。绿巨人浩克把洛基摔了又摔，洛基不得已说出了正确的密码（字符串b）。请你帮助美国队长计算他最少需要操作多少次才能打开密码箱，夺回宇宙魔方。

输入格式:
第一行输入字符串a，长度不大于 10001000，只包含小写字母，表示密码箱上的初始文字。
第二行输入字符串b，只包含小写字母，保证长度和第一个字符串相等，表示正确密码。
第三行输入一个整数 n(0 \le n \le 676)n(0≤n≤676)。
接下来 nn 行，每行输入两个空格隔开的字符 X i, Y i，表示操作规则：一次操作能把一个字符 X i变换成字符 Y i。

输出格式:
如果密码箱能被打开，输出最少的操作次数。否则输出 -1。

样例输入:
dabc
dddd
3
a b
b c
c d

样例输出:
6

Answer 1

#include<bits/stdc++.h>
using namespace std;
char a[1005],b[1005],e,f;
int n,d[27][27],s=0;
int main(){
cin>>a>>b;
cin>>n;
for(int i=0;i<n;i++){
cin>>e>>f;
d[e-'a'][f-'a']=d[f-'a'][e-'a']=1;
}
for(int k=0;k<26;k++){
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(d[i][k]!=0&&d[k][j]!=0&&i!=j){
if(d[i][j]==0) d[i][j]=d[i][k]+d[k][j];
else d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
for(int i=0;i<strlen(a);i++){
s+=d[a[i]-'a'][b[i]-'a'];
}
cout<<s;
return 0;
}