本文共 2344 字，大约阅读时间需要 7 分钟。
首先，我们需要从字符串中提取整数值。例如，对于字符串s，可以使用sprintf函数将其转换为整数值并保存在变量n中。以下是示例代码：
#includeusing namespace std; // 例如，字符串s = "1234"可以转换为整数值n = 1234 sprintf("n", "%d", s); // 或者使用scanf函数 sscanf("n", "%d", &n);
这是一个简单的示例，展示了如何从字符串中提取整数值。这是编程中的常见操作，尤其是在处理用户输入时非常有用。在我们的程序中，我们将使用类似的方法来读取输入数据。
下方是完整的代码示例：
#include#include #include #include #include using namespace std; #define N 10000 int prime[N]; int s, e, vis[N]; // 检查一个数是否为质数 int Prime(int x) { for (int i = 2; i <= sqrt(x); i++) { if (x % i == 0) return 0; } return 1; } // 将数字的某一位设置为0 int change(int n, int pos) { char s[10]; sprintf(s, "%d", n); s[pos] = '0'; sscanf(s, "%d", &n); return n; } // 广度优先搜索找到从s到e的最短路径，并计算成本 int bfs(int start, int end) { memset(vis, 0, sizeof(vis)); queue q; q.push(start); vis[start] = 1; int w = 1000; // 每一步的权重为1000的一位数（0到9） while (!q.empty()) { int u = q.front(); q.pop(); if (u == end) return vis[u] - 1; for (int i = 0; i < 4; i++) { int v = change(u, i); // 将u的第i位数字设置为0 for (int j = 0; j < 10; j++) { int next = v + j * w; if (prime[next] && !vis[next]) { q.push(next); vis[next] = vis[u] + 1; } } w /= 10; // 下一个位置的权重是当前权重的十分之一 } } return -1; // 如果无法到达 } // 主函数 int main() { // 初始化质数数组 for (int i = 1000; i < N; i++) { prime[i] = Prime(i); } // 读取输入 int T; scanf("%d", &T); for (int i = 0; i < T; i++) { int s, e; scanf("%d %d", &s, &e); // 调用广度优先搜索算法 if (bfs(s, e) == -1) { printf("Impossible\n"); } else { printf("%d\n", bfs(s, e)); } } return 0; }
质数检查：
我们首先需要在代码中定义一个质数数组prime，用于存储每个数是否为质数。代码中定义了一个名为Prime的函数，用于以线性时间复杂度检查一个数是否为质数。数字改变函数：
为了实现数位逐步改变的功能，我们定义了一个名为change的函数。该函数接收一个整数n和一个位置pos，然后将n的pos位置的数字设置为0，并重新解析这个修改后的字符串以获得新的整数值。广度优先搜索（BFS）：
主要算法部分是广度优先搜索，用于找到从初始数start到目标数end的最短路径。每次从队列中取出当前数，尝试将其每一位数字依次设置为0，生成下一个数，并检查该数是否为质数和未被访问。如果是，则将下一个数加入队列，并记录访问路径。每一步会增加一个计算成本，即为1。搜索过程中，每次从一个数到下一个数的转换涉及改变一个数位，并根据权重加上相应的计算成本。权重计算：
每条边的权重是当前数位的权重，比如从个位到十位的权重是10，而从十位到百位的权重则是100。具体来说，我们从个位开始，逐步将权重除以10，直到处理完所有的数位。主函数与输入处理：
在主函数中，我们首先初始化质数数组prime，然后读取输入数据。对于每个测试用例，我们从标准输入中读取两个四位数，分别是起点s和终点e。然后调用广度优先搜索函数bfs，找到从s到e的最短路径，并输出结果。如果路径不存在，则输出"Impossible"。通过上述代码，我们可以完成广度优先搜索驱动的数字逐位改变过程，从而找到两四位质数之间的最便宜路径（即计算最小的改变次数）。该算法充分利用了广度优先搜索的性质，确保找到一条最小改变次数的路径。
转载地址：http://zioez.baihongyu.com/