端脑
题目描述
涛涛是一个计算爱好者,他十分热衷于研究各种数字游戏。并扬言,这世间就没有我涛某人解决不了的数字问题。
于是,在一个月黑风高的晚上,他被打晕拖上了面包车……
当他醒来的时候,发现自己处在一个巨大的广场内,这个广场的每一块地板上都有一个4位数的编号。突然广场上
的喇叭响起了声音:"欢迎来到端脑,你是前来挑战的第 79834817 名选手,你和前面的每一位选手一样都十分的聪明,
但是他们都没能从这关活着出去。如你所见,广场的每一个地板上都有一个 4 位数的编号,你现在所处的地板编号为 Q,
是一个素数,出口的编号为 W,也是一个素数,想要通关,很明显,你需要走到出口 W,但是你的移动,需要遵循一定
的规律。你每次移动后的地板,只能有一位数字进行改变,并且这个地板编号也得是一个素数,只有经过最少次数的
移动到达出口 W,才能通过这一关,祝你好运……"出于人道主义,请你帮助涛涛计算出从当前地板编号 Q 到达出口
地板编号 W,最少的移动次数是多少?
提示
0<T<=100,1000<=Q,W<=9999,变换过程中的数也是在 1000∼9999 之间
输入格式
第一行一个整数 T,表示测试数据组数
接下来 T 行,每行两个整数 Q,W
输出格式
T 行,每行一个数字表示答案,如果无法做到或不需要操作,请输出 0
算法分析:
从 Q 到 W 最少需要的步数,可以考虑广搜。广搜的每一步都是去选择四位数当中的某一位进行改变,同时又需要改变之后的数是素数。如果在广搜的过程中判断素数,那时间复杂度会很高,因此可以先预处理出每个数是不是素数(这里用的是埃氏筛,当然用 NSQRT(N) 的算法时间也是允许的)。
参考代码