题目链接
dfs初步 题目很直白，就是不断地搜索下一个符合条件的数字，最后输出最短路径
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAX_N = 10000 + 10; int prime[MAX_N]; //挑战程序设计竞赛求素数的模板 bool is_prime[MAX_N + 1]; int sieve(int n) { int p = 0; for (int i = 0; i <= n; i++) { is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; } } } return p; } int dp[MAX_N]; //路径的存储 //number为传来的数字，digit为改变数的位数，change为换为哪位数 int get_next(int number, int digit, int change) //下一个状态的查找 { switch (digit) { case 0: return number / 10 * 10 + change; case 1: return number / 100 * 100 + number % 10 + change * 10; case 2: return number / 1000 * 1000 + number % 100 + change * 100; case 3: return number % 1000 + change * 1000; } return 0; } int main() { int N; sieve(MAX_N); cin >> N; while (N--) { int from, to; cin >> from >> to; queue<int> que; memset(dp, 0x7f, sizeof(dp)); //0x7f为memset对int能赋的最大值 dp[from] = 0; que.push(from); while (que.size()) { int current = que.front(); que.pop(); for (int i = 0; i < 10; i++) //digit { for (int j = 0; j < 4; j++) //change { if (i == 0 && j == 3) continue; int next = get_next(current, j, i); if (is_prime[next] == false || dp[next] <= dp[current]) continue; dp[next] = dp[current] + 1; //开dp存放路径，分别为1 2 3 4.....下标表示第几次转化成为的数 que.push(next); } } } cout << dp[to] << endl; } return 0; }虽然是初步但是本蒟蒻还是写了好多次. …还是多做点题多吧
