题解：P6937 [ICPC2017 WF] Secret Chamber at Mount Rushmore

· · 题解

题目大意：

给出 m 种字母转换关系，再有 n 个询问，判断给定的字符串 s 是否能转换成字符串 t 。

思路：

用 map 把每种字母转换关系映射进来，由于一个字符可能会有多种转换关系，所以 map 定义的第二个要写成 vector<char> 。

接下来判断的时候，先判断两个字符串长度是否相等，否则输出 no ，是则循环 dfs 。

dfs 的时候可以用一个变量记录是否转换到当前字符，别忘了还有一个标记数组。而当前字符如果为 char(0) 就是递归边界。接下来就枚举 map 里的 vector 每次只要当前要转换的字符没被标记过就 dfs 这个字符。

参考文献

dfs:

void dfs(char x, char y){
    if (x == y){
        flag = 1;
        return;
    }
    v[int(x)] = 1;
    if (x == char(0)) return;
    for (int i = 0; i < a[x].size(); i++)
        if (!v[int(a[x][i])])
            dfs(a[x][i], y);
}

map 定义： map<char, vector<char>> a;

最终代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
bool flag = 0;
string s1, s2;
int v[N];
map<char, vector<char>> a;
void dfs(char x, char y){
    if (x == y){
        flag = 1;
        return;
    }
    v[int(x)] = 1;
    if (x == char(0)) return;
    for (int i = 0; i < a[x].size(); i++)
        if (!v[int(a[x][i])])
            dfs(a[x][i], y);
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        char b, c;
        cin >> b >> c;
        a[b].push_back(c);
    }
    while (m--){
        cin >> s1 >> s2;
        if (s1.size() != s2.size()){
            cout << "no" << endl;
            continue;
        }
        bool k = 0;
        for (int i = 0; i < s1.size(); i++)
            if (s1[i] != s2[i]){
                dfs(s1[i], s2[i]);
                if (!flag) k = 1;
                flag = 0;
                memset(v, 0, sizeof v);
            }
        if (!k) cout << "yes";
        else cout << "no";
        puts("");
    }
    return 0;
}