本文主要是介绍coj1090: Number Transformation bfs,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这道题用bfs做,一开始没理解清题意WA的不要不要的,后来仔细看题发现A是一步变一次的,也就是说每次可以加的素数的范围是改变的,比如当S=5,T=20的时候,S先加3=8,然后此时可以取的素数就不仅有2、3,还有5、7了,一开始不仔细看题真是醉了。
Description
In this problem, you are given a pair of integers A and B. You can transform any integer number A to B by adding x to A.This x is an integer number which is a prime below A.Now,your task is to find the minimum number of transformation required to transform S to another integer number T.
Input
Input contains multiple test cases.Each test case contains a pair of integers S and T(0< S < T <= 1000) , one pair of integers per line.
Output
For each pair of input integers S and T you should output the minimum number of transformation needed as Sample output in one line. If it's impossible ,then print 'No path!' without the quotes.
Sample Input
5 7 3 4
Sample Output
Need 1 step(s)No path!
bfs注意不要重复放一个数,不然队列就爆了,然后可以将素数先打表,我这里还将每个数的前一个最大素数打表了,用的时候有种链表的快感
下面是AC代码
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int preprime[1005], prime[1005] = { 0 }; void bfs(int S,int T,int step[], int vis[]) {int temp1, ts;queue<int>p;step[S] = 1;p.push(S);while (!p.empty()){temp1 = p.front();ts=temp1;p.pop();while (preprime[ts] != 0){if (temp1 + preprime[ts]<T){if (vis[temp1 + preprime[ts]] == 0){p.push(temp1 + preprime[ts]);step[temp1 + preprime[ts]] = step[temp1] + 1;vis[temp1 + preprime[ts]]=1;}}else if (temp1 + preprime[ts] == T){cout << "Need " << step[temp1] << " step(s)" << endl;return;}ts = preprime[ts];}}cout << "No path!" << endl; } int main() {int S, T;int step[1005] = {0};int vis[1005] = {0};int temp = 0;for (int i = 2; i<502; i++)for (int j = 2 * i; j<1002; j += i)prime[j] = 1;for (int i = 2; i<1002; i++){preprime[i] = temp;if (prime[i] == 0)temp = i;}while (scanf("%d%d",&S,&T)==2){if(S==1||S==2)cout << "No path!" << endl;else{for(int i=0;i<T;i++){vis[i]=0;step[i]=0;}bfs(S,T,step, vis);}}return 0; }
这篇关于coj1090: Number Transformation bfs的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!