[POJ - 3126 ]E - Prime Path
题目阅读
生词
cabinet [ˈkæbɪnət] n.内阁
every now and then 偶尔
eavesdrop [ˈi:vzdrɒp] vi. 偷听
intervened [ˌɪntəˈvi:nd] v. 介入
expenditure [ɪkˈspendɪtʃə®] n. 花费
Prime minister n.首相
prime n.素数
invent [ɪnˈvent] vt. 创造
scheme [ski:m] n.计划
happen to do 碰巧做某事
guru [ˈgʊru:] n. 专家
题意是有四位数字的素数且最高位不为0的门牌号，如果修改一位需要1磅，并且每次修改的结果都必须是素数，需要找出一条从起始门票号到目标门牌号的修改路径，这条路径的花费要求最小化。
我们可以理解为每个节点代表门牌号，寻找两个素数节点的最短路的问题，无疑要用到BFS。
而生成一个新的素数无疑要修改原数的一位的值，并且要排除重复访问的情况（修改后不能和原数一样，也不能是曾经访问过的数，否则就不满足最短路的必要条件）。似乎容易认为原数是有4个结点的树，每个节点都有9或10种修改的可能。其实可以引用《啊哈算法》再解炸弹人的思路：对于每个结点的修改作为一个单独的方向进行搜索，枚举该位上的各种可能形成临时4位数，如果是素数且未访问过则入队（新节点）。
为何不考虑一次修改一个数的多位？因为题目中要求“a path of prime numbers where only one digit is changed from one prime to the next prime.”——每次改变只能修改一个数字。
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
输入的门牌号都是4位素数且最高位不为0。
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
输出最短路的花费或者没有路。
退化情况
1.输入的数值不符合门牌号规则
输入的规则已经排除了这一情况
2.尝试的数值是目标数
结束BFS，输出步数。那么需要用结构体记录当前数值与步数。
struct node{int p,step;
};
temp=que.front();if(temp.p==y){cout<用flag表示找到目标数，用以和找不到目标的区分。
3.修改后的结果不是素数
则不入队，尝试继续修改。这里需要调用判断素数函数，因为需要判断的次数很多。
int isP(int x){for(int i=2;i*i<=x;i++){if(x%i==0){return 0;}}return 1;
}
注意sqrt返回值类型导致i<=sqrt(x)错误，这里直接用i*i<=x表示。
返回非素数0的条件是找到x的因子i，即x%i==0；如果找不到因子，那么x就是素数。
尝试过生成素数表，但是网上题解直接用素数判断函数，虽然这个函数多次调用相对查素数表的时间复杂度可能很大，但至少在题目允许范围内。
4.没有路
由于每次改变只能修改一个数字，对原数每位各自修改后仍然找不出他的素数后继，那么只能认为没有路。在队列角度上就是没有新节点入队导致队空，此时输出impossible.
5.修改后的结果和原数一样,或者访问过这个素数
这就形成了自环，不符合DAG，不入队，继续修改。二者可以通过是否访问过该节点排除。
if(!vis[trial]&&isP(trial))
一般情况
拆分数字：把每位看做修改的大方向，一共有四个方向，每个方向的可能范围是[1,9]（最高位不为0）、[0,9]（其余位），枚举所有可能，对所有符合要求的可能入队并标记。
for(j=0;j<=9;j++){trial=temp.p/10*10+j;if(!vis[trial]&&isP(trial)){vis[trial]=1;t.p=trial;t.step=temp.step+1;que.push(t);}}for(j=0;j<=9;j++){trial=temp.p/100*100+j*10+temp.p%10;if(!vis[trial]&&isP(trial)){vis[trial]=1;t.p=trial;t.step=temp.step+1;que.push(t);}}for(j=0;j<=9;j++){trial=temp.p/1000*1000+j*100+temp.p%100;if(!vis[trial]&&isP(trial)){vis[trial]=1;t.p=trial;t.step=temp.step+1;que.push(t);}}for(j=1;j<=9;j++){trial=j*1000+temp.p%1000;if(!vis[trial]&&isP(trial)){vis[trial]=1;t.p=trial;t.step=temp.step+1;que.push(t);}}
枚举可能需要注意不同位的范围不同、用**/和%**获取其它位的数值来组合出试探数。
最后，贴上完整代码
#include
#include
#include
using namespace std;
struct node{int p,step;
};
int vis[10000];
int isP(int x){for(int i=2;i*i<=x;i++){if(x%i==0){return 0;}}return 1;
}
int main(){int n,i,j,x,y,step,trial,flag=0;struct node t,temp;freopen("test2.txt","r",stdin);cin>>n;for(i=1;i<=n;i++){cin>>x>>y;flag=0;queue que;memset(vis,0,sizeof(vis));if(x==y){cout<<"0"< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！