每周一赛（E题，广搜求方案）
Description
In this problem, you are given an integer number s. You can transform any integer number A to another integer number B by adding x to A. This xis an integer number which is a prime factor of A (please note that 1 and A are not being considered as a factor of A). Now, your task is to find the minimum number of transformations required to transform s to another integer number t.
Input
Input starts with an integer T (≤ 500), denoting the number of test cases.
Each case contains two integers: s (1 ≤ s ≤ 100) and t (1 ≤ t ≤ 1000).
Output
For each case, print the case number and the minimum number of transformations needed. If it's impossible, then print -1.
Sample Input
2
6 12
6 13
Sample Output
Case 1: 2
Case 2: -1
题意：
例如：6+3=9，9+3=12加了两次
6+3=9，9+3=12，12的质因数只有2，3所以这种方案不行
6+2=8，8+2=10，10的质因数只有2，5所以不行
所以例二输出-1
利用搜索的方法，每次都枚举当前数的所有质因数，而且这里不需要标记，直到当前记录值等于目标值，这时也不要返回，用一个开始赋值很大的数来不断地更新最小值。
这么一来的话，就真的是每种情况都得枚举到了，这是会超时的！虽然我特意舍弃DFS而用了BFS还是不能幸免~~~~~
所以要进行优化，用一个开始赋值非常大的数组，然后每次记录当前入队列的节点他的当前值是什么，记下他的当前走了几步，后面每次当一个节点进队列时，就可以判断一下
他当前的步数是否小于以前走过的，如果小于就入队列，不小于就不进，这样就减少了很多毫无意义的尝试了
最后不得不说一句，做质因数标记那个数组在程序输入之前自动做好就行了，也花不了多少时间，而我竟然多次一举，去写了个辅助程序........................
#include"iostream"
#include"algorithm"
#include"cstring"
#include"cstdio"
#include"queue"
using namespace std;
int book[1010];
int mark[1010];
struct node
{
int as;
int step;
}; const int maxn=1000000000;
int ans=1000000000;
int flag;
int c;
int a;
int b;
int step=0; void BFS()
{
memset(mark,0x3f,sizeof(mark));
queue<struct node> que;
struct node cc,e,t;
cc.as=a;
cc.step=0;
que.push(cc);
while(!que.empty())
{
e=que.front();
que.pop();
if(e.as==b)
{
if(ans>e.step) ans=e.step;
}
for(int i=2;i<e.as;i++)
{
if(e.as%i) continue;
if(book[i]!=1) continue;
//cout<<"iqian"<<i<<endl;
// cout<<i<<endl;
if(mark[e.as+i]>e.step+1)
{
t=e;
t.as+=i;
if(t.as>b) continue;
t.step++;
mark[t.as]=t.step;
que.push(t);
}
}
}
} int main()
{
int n,f;
book[1]=1;
book[2]=1;
book[3]=1;
book[5]=1;
book[7]=1;
book[11]=1;
book[13]=1;
book[17]=1;
book[19]=1;
book[23]=1;
book[29]=1;
book[31]=1;
book[37]=1;
book[41]=1;
book[43]=1;
book[47]=1;
book[53]=1;
book[59]=1;
book[61]=1;
book[67]=1;
book[71]=1;
book[73]=1;
book[79]=1;
book[83]=1;
book[89]=1;
book[97]=1;
book[101]=1;
book[103]=1;
book[107]=1;
book[109]=1;
book[113]=1;
book[127]=1;
book[131]=1;
book[137]=1;
book[139]=1;
book[149]=1;
book[151]=1;
book[157]=1;
book[163]=1;
book[167]=1;
book[173]=1;
book[179]=1;
book[181]=1;
book[191]=1;
book[193]=1;
book[197]=1;
book[199]=1;
book[211]=1;
book[223]=1;
book[227]=1;
book[229]=1;
book[233]=1;
book[239]=1;
book[241]=1;
book[251]=1;
book[257]=1;
book[263]=1;
book[269]=1;
book[271]=1;
book[277]=1;
book[281]=1;
book[283]=1;
book[293]=1;
book[307]=1;
book[311]=1;
book[313]=1;
book[317]=1;
book[331]=1;
book[337]=1;
book[347]=1;
book[349]=1;
book[353]=1;
book[359]=1;
book[367]=1;
book[373]=1;
book[379]=1;
book[383]=1;
book[389]=1;
book[397]=1;
book[401]=1;
book[409]=1;
book[419]=1;
book[421]=1;
book[431]=1;
book[433]=1;
book[439]=1;
book[443]=1;
book[449]=1;
book[457]=1;
book[461]=1;
book[463]=1;
book[467]=1;
book[479]=1;
book[487]=1;
book[491]=1;
book[499]=1;
book[503]=1;
book[509]=1;
book[521]=1;
book[523]=1;
book[541]=1;
book[547]=1;
book[557]=1;
book[563]=1;
book[569]=1;
book[571]=1;
book[577]=1;
book[587]=1;
book[593]=1;
book[599]=1;
book[601]=1;
book[607]=1;
book[613]=1;
book[617]=1;
book[619]=1;
book[631]=1;
book[641]=1;
book[643]=1;
book[647]=1;
book[653]=1;
book[659]=1;
book[661]=1;
book[673]=1;
book[677]=1;
book[683]=1;
book[691]=1;
book[701]=1;
book[709]=1;
book[719]=1;
book[727]=1;
book[733]=1;
book[739]=1;
book[743]=1;
book[751]=1;
book[757]=1;
book[761]=1;
book[769]=1;
book[773]=1;
book[787]=1;
book[797]=1;
book[809]=1;
book[811]=1;
book[821]=1;
book[823]=1;
book[827]=1;
book[829]=1;
book[839]=1;
book[853]=1;
book[857]=1;
book[859]=1;
book[863]=1;
book[877]=1;
book[881]=1;
book[883]=1;
book[887]=1;
book[907]=1;
book[911]=1;
book[919]=1;
book[929]=1;
book[937]=1;
book[941]=1;
book[947]=1;
book[953]=1;
book[967]=1;
book[971]=1;
book[977]=1;
book[983]=1;
book[991]=1;
book[997]=1;
cin>>n;
f=1;
while(n--)
{ cin>>a>>b;
c=b-a;
if(c<0) cout<<"Case "<<f++<<": "<<-1<<endl;
else
{
BFS();
if(ans!=1000000000) cout<<"Case "<<f++<<": "<<ans<<endl;
else cout<<"Case "<<f++<<": "<<-1<<endl;
ans=1000000000;
}
}
return 0;
}
最新文章
- JavaScript中函数函数的定义与变量的声明<基础知识一>
- TypeError: coercing to Unicode: need string or buffer, ChatRoom found
- pkg-config
- [转]SQL Server字符串处理函数大全
- 如何正确使用Cocoapods
- 23. Sum Root to Leaf Numbers
- Coded UI Test中的数据驱动测试
- .Net规则引擎介绍 - REngine
- c++11 gcc4.8.x安装
- 基于EasyUI实现windows桌面
- uva 12626 - I ❤ Pizza
- yacc和lex在ubuntu上安装
- 预处理指令中#Pragma
- HDU 6112 今夕何夕
- [转载] NodeJS无所不能：细数十个令人惊讶的NodeJS开源项目
- cocos creator主程入门教程（三）—— 资源管理
- RF经验~~
- hadoop用户写入文件权限不够的问题
- plink:ped格式转换为bed格式
- 分布式监控系统Zabbix-3.0.3-完整安装记录 - 添加shell脚本监控