LeetCode 1625. 执行操作后字典序最小的字符串（BFS）

示例 1：
输入：s = "5525", a = 9, b = 2
输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"​​​​​​​​​​​​
无法获得字典序小于 "2050" 的字符串。

示例 2：
输入：s = "74", a = 5, b = 1
输出："24"
解释：执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"​​​​​​​​​​​​
无法获得字典序小于 "24" 的字符串。

示例 3：
输入：s = "0011", a = 4, b = 2
输出："0011"
解释：无法获得字典序小于 "0011" 的字符串。

示例 4：
输入：s = "43987654", a = 7, b = 3
输出："00553311"
 
提示：
2 <= s.length <= 100
s.length 是偶数
s 仅由数字 0 到 9 组成
1 <= a <= 9
1 <= b <= s.length - 1

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        unordered_set<string> vis;//记录已经出现的状态
        string cur, nt, minstr = s;
        int i, n = s.size(), bit;
        vis.insert(s);
        queue<string> q;
        q.push(s);
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            if(cur < minstr)
                minstr = cur;
            nt = cur;
            for(i = 1; i < n; i+=2)
            {	//奇数位加 a
                bit = (cur[i]-'0'+a)%10;
                nt[i] = bit+'0';
            }
            if(!vis.count(nt))
            {
                vis.insert(nt);
                q.push(nt);
            }
            // 向右轮转
            nt = cur.substr(n-b)+cur.substr(0,n-b);
            if(!vis.count(nt))
            {
                vis.insert(nt);
                q.push(nt);
            }
        }
        return minstr;
    }
};