POJ3126 Prime Path【数论】【BFS】

2024-06-15 04:48
文章标签 bfs path 数论 prime poj3126

本文主要是介绍POJ3126 Prime Path【数论】【BFS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:

http://poj.org/problem?id=3126


题目大意:

给你两个有四位数字的素数 A、B,问:每次只改变一个数字,且改变前后的数都是

素数,那么从 A 变到 B,最少需要多少次。


解题思路:

用 BFS 来做。判断素数用筛法求素数打表预处理一下,不过注意 1000 以下的数要

当非素数看待。

每次改变一位数字,并且如果改变后的数仍为素数的话入队,并用 cnt[] 来记录步数。

直到得到目标数的时候,返回结果。


AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 10100;bool Prime[MAXN];void IsPrime()
{Prime[0] = Prime[1] = false;for(int i = 2; i < MAXN; ++i)Prime[i] = true;for(int i = 2; i < MAXN; ++i){if(Prime[i]){for(int j = i+i; j < MAXN; j+=i)Prime[j] = false;}}for(int i = 2; i < 1000; ++i)Prime[i] = false;
}
bool vis[MAXN];
int t[5],cnt[MAXN];int Bfs(int S,int T)
{queue<int> q;memset(vis,false,sizeof(vis));memset(cnt,0,sizeof(cnt));q.push(S);vis[S] = true;while(!q.empty()){int v = q.front();q.pop();//存取各个位上数字t[0] = v/1000;t[1] = v/100%10;t[2] = v/10%10;t[3] = v%10; t[0]=v/1000;//    printf("%d %d %d %d\n",t[0],t[1],t[2],t[3]);for(int j = 0; j < 4; ++j){int temp = t[j];    //记录第 j 个数字for(int i = 0; i <= 9; ++i) //将 t[j] 改变为 i{if(i != temp){t[j] = i;int vtemp = t[0]*1000 + t[1]*100 + t[2]*10 + t[3];if(!vis[vtemp] && Prime[vtemp]){cnt[vtemp] = cnt[v] + 1;vis[vtemp] = true;q.push(vtemp);}if(vtemp == T)return cnt[vtemp];}}t[j] = temp;    //变回原本数字,继续改变另外数字}if(v == T)return cnt[v];}return -1;
}int main()
{int T,A,B;IsPrime();scanf("%d",&T);while(T--){scanf("%d%d",&A,&B);int Ans = Bfs(A,B);if(Ans == -1)printf("Impossible\n");elseprintf("%d\n",Ans);}return 0;
}


这篇关于POJ3126 Prime Path【数论】【BFS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1062467

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

POJ2247数论

p = 2^a*3^b*5^c*7^d 求形如上式的第n小的数。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.u

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数?条件:举例说明:一般化: 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法:举几个例子:例子 1: 计算 12 和 18

CSP-J基础之数学基础 初等数论 一篇搞懂(二)

文章目录 前言算术基本定理简介什么是质数?举个简单例子:重要的结论:算术基本定理公式解释:举例: 算术基本定理的求法如何找出质因数:举个简单的例子: 重要的步骤:C++实现 同余举个例子:同余的性质简介1. 同余的自反性2. 同余的对称性3. 同余的传递性4. 同余的加法性质5. 同余的乘法性质 推论 总结 前言 在计算机科学和数学中,初等数论是一个重要的基础领域,涉及到整数