3712 - Prime Path
描述
阿P给阿K两个素数A,B，保证A,B位数相同且为4位或5位。阿K只能对A作一种操作：将其中一位数字改成另一个数字，要求每次操作后得到的数还是素数，问最少多少次可以从A变到B。
输入
第一行一个整数 n，代表有 n 组数据。
对于每组数据，输入一行两个四位或五位素数 A,B。
输出
对于每组数据输出一行最少操作次数。无解输出 No solution。
样例

输入

1
1033 8179

输出

6
提示
把同位数素数看作点，改一位仍为素数则连边，BFS求最短路；首位不能改成0(保持位数)。
来源
51nod 3016
标签
BFS 图论 素数 普及+
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1
统计
上一题
下一题