博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
简单BFS POJ 3126 Prime Path
阅读量:4839 次
发布时间:2019-06-11

本文共 2735 字,大约阅读时间需要 9 分钟。

题目大意就是输入一个T然后输入一个素数,再输入另一个数,输入第一个数变成另一个所需要的最少步数。

代码:

View Code
1 #include 
2 #include
3 #include
4 5 using namespace std; 6 7 int vis[10005]; 8 int prim[10005],leap; 9 struct node 10 { 11 int n[5],step; 12 int num; 13 }q[4*10005]; 14 void make_prim() 15 { 16 memset(prim,0,sizeof(prim)); 17 int flag = 1,i,j; 18 for(i = 1001;i <= 9999;i += 2) 19 { 20 flag = 1; 21 for(j = 2;j <= i/2;j++) 22 { 23 if(i%j == 0) 24 { 25 flag = 0; 26 break; 27 } 28 } 29 prim[i] = flag; 30 31 } 32 } 33 int num,f,r,target; 34 void get() 35 { 36 int n; 37 n = q[f].num; 38 39 q[f].n[4] = n%10; 40 n /= 10; 41 q[f].n[3] = n%10; 42 n /= 10; 43 q[f].n[2] = n%10; 44 n /= 10; 45 q[f].n[1] = n; 46 } 47 int getsum(struct node temp) 48 { 49 return temp.n[1]*1000+temp.n[2]*100+temp.n[3]*10+temp.n[4]; 50 } 51 void bfs() 52 { 53 int i,j; 54 memset(vis,0,sizeof(vis)); 55 f = r = 0; 56 q[r].num = num; 57 q[r].step = 0; 58 get(); 59 r++; 60 vis[num] = 1; 61 leap = 0; 62 while(f < r) 63 { 64 struct node temp,now; 65 get(); 66 now = q[f]; 67 now.step = q[f].step+1; 68 f++; 69 for(i = 0;i < 10;i++) 70 { 71 for(j = 1;j < 5;j++) 72 { 73 temp = now; 74 if(i != temp.n[j]) 75 { 76 temp.n[j] = i; 77 temp.num = getsum(temp); 78 79 if(!vis[temp.num] && prim[temp.num]) 80 { 81 vis[temp.num] = 1; 82 q[r] = temp; 83 if(temp.num == target) 84 { 85 leap = 1; 86 break; 87 } 88 r++; 89 } 90 } 91 } 92 if(leap) 93 break; 94 } 95 if(leap) 96 break; 97 } 98 return ; 99 }100 int main()101 {102 int t;103 make_prim();104 scanf("%d",&t);105 106 while(t--)107 {108 scanf("%d %d",&num,&target);109 if(num == target)110 {111 puts("0");112 continue;113 }114 115 bfs();116 if(leap)117 printf("%d\n",q[r].step);118 else119 printf("Impossible\n");120 121 }122 123 return 0;124 }

转载于:https://www.cnblogs.com/0803yijia/archive/2012/09/07/2675390.html

你可能感兴趣的文章
SpringBoot集成jsp
查看>>
HTML+CSS 内容居中效果
查看>>
关于对话框
查看>>
Jmeter-元件的作用域和执行顺序
查看>>
ArrayList集合
查看>>
Redis集群搭建与简单使用
查看>>
VS2010连接SQLite数据库
查看>>
30分钟学会如何使用Apache Shiro
查看>>
asp.net部署时加密config文件
查看>>
想开个网店的。。学习一下vancl的分析
查看>>
DDD:在基于关系数据库的领域,聚合的边界等于并发管理的边界。
查看>>
poj 1961 Period
查看>>
BZOJ1560: [JSOI2009]火星藏宝图
查看>>
play framework 相关
查看>>
cf1008 codeforces round #535(div3) E1. Array and Segments (Easy version)
查看>>
React 学习笔记
查看>>
LeetCode_Combinations
查看>>
快手第一题
查看>>
有向图强连通分量的Tarjan算法及模板
查看>>
MEAN教程3-NPM安装
查看>>