蒜头君被暗黑军团包围在一座岛上，所有通往近*团的路都有暗黑军团把手。幸运的是，小岛上有一扇上古之神打造的封印之门，可以通往近*团，传闻至今没有人能解除封印。
封印之门上有一串文字，只包含小写字母，有 kk种操作规则，每个规则可以把一个字符变换成另外一个字符。经过任意多次操作以后，最后如果能把封印之门上的文字变换成解开封印之门的文字，封印之门将会开启。
蒜头君战斗力超强，但是不擅计算，请你帮忙蒜头君计算至少需要操作多少次才能解开封印之门。
输入格式
输入第一行一个字符串，长度不大于 10001000，只包含小写字母，表示封印之门上的文字。
输入第二行一个字符串，只包含小写字母，保证长度和第一个字符串相等，表示能解开封印之门的文字。
输入第三行一个整数 k(0 \le k \le 676)k(0≤k≤676)。
接下来 kk 行，每行输出两个空格隔开的字符 aa, bb，表示一次操作能把字符 aa 变换成字符 bb。
输出格式
如果蒜头君能开启封印之门，输出最少的操作次数。否则输出一行 -1−1。
样例输入
abcd dddd 3 a b b c c d
样例输出
6
一个简单的bfs，看到求最小步数应该是第一反应，但是还是先用dfs写了一遍，可能是因为经常用dfs把。。。
#include<queue> #include<cmath> #include<cstdio> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define maxn 1010 #define debug(a) cout << #a << " " << a << endl using namespace std; typedef long long ll; int mapn[maxn][maxn] = {0}, ans = 0, flag, vis[maxn]; vector<int>E[maxn]; /*void dfs( int x, int y, int cnt ) { if( mapn[x][y] == 1 ) { ans += cnt; flag = 1; return ; } for( int i = 0; i < E[x].size(); i ++ ) { if( !vis[E[x][i]] ) { vis[E[x][i]] = 1; dfs( E[x][i], y, cnt + 1 ); vis[E[x][i]] = 0; } } }*/ struct node { int num,step; }; void bfs( int x, int y ) { queue<node> q; node p; p.num = x, p.step = 0; q.push(p); while( !q.empty() ) { node now = q.front(); q.pop(); /*debug( now.step ); debug( now.num );*/ if( now.num == y ) { ans += now.step; flag = 1; //debug( ans ); return; } for( int i = 0; i < E[now.num].size(); i ++ ) { if( !vis[E[now.num][i]] ) { vis[E[now.num][i]] = 1; node tmp; tmp.num = E[now.num][i], tmp.step = now.step + 1; q.push(tmp); } } } } int main() { string s1,s2; cin >> s1 >> s2; int T; cin >> T; while( T -- ) { char a,b; cin >> a >> b; mapn[a-'a'][b-'a'] = 1; E[a-'a'].push_back(b-'a'); } int i; for( i = 0; i < s1.length(); i ++ ) { if( s1[i] != s2[i] ) { flag = 0; memset( vis, 0, sizeof(vis) ); vis[s1[i]-'a'] = 1; bfs( s1[i]-'a', s2[i]-'a' ); if( !flag ) { cout << "-1" << endl; break; } } } if( i == s1.length() ) { cout << ans << endl; } return 0; }