第二场（B2-破译密码）

链接：https://ac.nowcoder.com/acm/contest/6357/B
来源：牛客网

题目描述：
牛牛收到了一个任务，任务要求牛牛破译一个密码。牛牛将被给予两个字符串s1和s2，均由四个小写字母构成。需要破译的密码为从s1变换到s2最少需要的变换次数。
变换的方式是这样：每次变换可以选择当前字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上2，3，5，若是超出'z'，则重新从'a'开始，例如：对于字符串"abcd"，我们选择'c'的位置进行变换，则变换之后的字符串为"ceci";对于字符串"qyzr",我们选择'r'位置进行变换，则变换之后的字符串为"sber"。

输入
"aaaa","ccgk"
输出
2
说明：第一次变换选择第一个'a'，变成"acdf"，第二次变换选择第二个'c'，变成"ccgk"，故答案为2
备注:
s1,s2均由四个小写字母组成
解题思路：
“最少变换次数”，可以使用bfs。常规的广搜套路，根据当前结点变换得到下一结点，同时利用集合判断是否访问过，如果未访问就入队。
代码：

#include <bits/stdc++.h>
class Solution {
public:
    /**
     * 返回最终的答案
     * @param s1 string字符串 表示初始的字符串
     * @param s2 string字符串 表示目标的字符串
     * @return int整型
     */
    int solve(string s1, string s2) {
        // write code here
        if(s1 == s2) return 0;
        int cnt = 0;
        queue<string> q;
        unordered_set<string> st;
        q.push(s1);
        st.insert(s1);
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                string t = q.front();
                if(t == s2) return cnt;
                q.pop();
                for(int i = 0; i < 4; ++i) {
                    string s = fun(t, i);
                    if(!st.count(s)) q.push(s), st.insert(s);
                }
            }
            ++cnt;
        }
        return -1;
    }

    string fun(string s, int x) {
        int j = 0;
        int add[] = {2, 3, 5};
        for(int i = 0; i < 4; ++i) {
            if(i != x) {
                s[i] = 'a' + (s[i] - 'a' + add[j]) % 26;
                ++j;
            }
        }
        return s;
    }
};