C++程序查找给定数字字符串所需的最小循环旋转次数，避免给定字符串集合

给定一个数字字符串 target ，长度为 N ，以及一个数字字符串 blocked ，每个字符串长度为 N 。任务是通过避免任何字符串转换成只包含 0 的原始字符串，找到将原始字符串转换为 target 所需的最小循环旋转次数。如果不可能，输出-1。

注意： 单个旋转意味着通过 1 单位增加或减少特定索引处的值。由于旋转是循环的，因此可以将0转换为9或将9转换为0。

示例：

输入： target = “7531”，blocked = {“1543”，“7434”，“7300”，“7321”，“2427”}

输出： 12

解释： “0000” -> “9000” -> “8000” -> “7000” -> “7100” -> “7200” -> “7210” -> “7310” -> “7410” -> “7510” -> “7520” -> “7530” -> “7531”

输入： target = “4231”，blocked = {“1243”，“4444”，“1256”，“5321”，“2222”}

输出： 10

实现： 为了解决这个问题，我们使用以下BFS方法：

创建一个长度为 N ，只包含 0 的字符串 start 。将其推送到队列中。队列被创建用于存储下一个可能的有效组合，该组合可以通过增加或减少一个字符来处理。
创建一个无序集合 avoid ，并将所有阻止的字符串添加到其中。
如果 start 或 target 在 avoid 中，那么无法达到所需的目标。
从队列中弹出 start 并遍历 start 的所有字符。通过保持其余常量不变，增加和减少每个字符一个单位，并检查字符串是否存在于 avoid 中。如果新的组合不等于target，并且不存在于 avoid 中，则将其推送到队列中，并插入 avoid 中，以防止在未来重复相同的组合。
一旦整个 start 的长度被遍历，对下一级执行相同的步骤。也就是说，对从 start 中获得并当前存在于队列中的有效字符串，重复以上步骤。
重复以上步骤，直到达到目标或没有进一步的组合，队列已变为空。
在任何时候，如果形成的字符串等于target，则返回 count 的值，该值保持BFS遍历的级数计数。count的值是所需的最小循环旋转次数。
如果不能获得更多的状态，并且队列为空，则输出 “Not Possible”。

// C++程序以计算最小的循环
//旋转次数
//以获得给定的数值字符串
//避免一组被阻止的字符串
 
#include <bits/stdc++.h>
using namespace std;
 
int minCircularRotations(
    string target,
    vector<string>& blocked,
    int N)
{
    string start = "";
    for (int i = 0; i < N; i++) {
        start += '0';
    }
 
    unordered_set<string> avoid;
 
    for (int i = 0; i < blocked.size(); i++)
        avoid.insert(blocked[i]);
 
    // 如果需要起始字符串
    // 避免
    if (avoid.find(start) != avoid.end())
        return -1;
 
    // 如果需要最终字符串
    // 避免
    if (avoid.find(target) != avoid.end())
        return -1;
 
    queue<string> qu;
    qu.push(start);
 
    // 变量用于存储旋转计数
    int count = 0;
 
    // BFS方法
    while (!qu.empty()) {
 
        count++;
 
        // 存储当前大小
        // 排队
        int size = qu.size();
 
        for (int j = 0; j < size; j++) {
 
            string st = qu.front();
            qu.pop();
 
            // 遍历字符串
            for (int i = 0; i < N; i++) {
 
                char ch = st[i];
 
                // 增加当前字符
                st[i]++;
 
                // 循环旋转
                if (st[i] > '9')
                    st[i] = '0';
 
                // 如果达到目标
                if (st == target)
                    return count;
 
                // 如果形成的字符串
                // 不是要避免的字符串之一
                if (avoid.find(st)
                    == avoid.end())
                    qu.push(st);
 
                // 将其添加到
                // 要避免的字符串列表中
                // 避免访问
                // 已经访问的状态
                avoid.insert(st);
 
                // 将当前值减小
                // 1并重复
                // 相似的检查
                st[i] = ch - 1;
 
                if (st[i] < '0')
                    st[i] = '9';
                if (st == target)
                    return count;
                if (avoid.find(st)
                    == avoid.end())
                    qu.push(st);
                avoid.insert(st);
 
                // 恢复原始
                // 字符
                st[i] = ch;
            }
        }
    }
 
    return -1;
}
 
// 驱动程序
int main()
{
    int N = 4;
    string target = "7531";
    vector<string> blocked
        = { "1543",
            "7434",
            "7300",
            "7321",
            "2427" };
 
    cout << minCircularRotations(
                target,
                blocked, N)
         << endl;
 
    return 0;
}

Output:

**时间复杂度：O(N 3 ) **

辅助空间：O(N)