题目描述（Prime Path, POJ 3126）：
给定两个四位数质数A和B，要求找到从A到B的最短转换路径，每次转换只能改变一个数字，并且转换后的数也必须是一个质数。
解题思路：
-
质数筛选：
- 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）生成所有四位数质数的列表。
-
图的构建：
- 将每个四位数质数看作图中的一个节点。
- 如果两个质数之间只有一个数字不同，则在这两个节点之间建立一条边。
-
广度优先搜索（BFS）：
- 从起始质数A开始，使用BFS搜索到目标质数B的最短路径。
详细步骤：
-
生成四位数质数列表：
- 初始化一个布尔数组
isPrime，标记1000到9999之间的每个数是否为质数。 - 使用筛法标记非质数。
- 收集所有标记为质数的四位数。
- 初始化一个布尔数组
-
构建邻接表：
- 对于每个四位数质数，尝试改变每一位（0-9），检查新数是否为质数且与原数不同。
- 如果是，则在邻接表中添加一条边。
-
BFS搜索最短路径：
- 使用队列进行BFS，记录每个节点的层次（即转换次数）。
- 从A开始，逐层扩展，直到找到B，记录转换次数。
代码实现（Python示例）：
def sieve_of_eratosthenes(max_num):
is_prime = [True] (max_num + 1)
p = 2
while (p p <= max_num):
if (is_prime[p] == True):
for i in range(p * p, max_num + 1, p):
is_prime[i] = False
p += 1
is_prime[0], is_prime[1] = False, False
return [p for p in range(1000, 10000) if is_prime[p]]
def build_adjacency_list(primes): adj_list = {prime: [] for prime in primes} for prime in primes: prime_str = str(prime) for i in range(4): for digit in '0123456789': if digit != prime_str[i]: new_num = int(prime_str[:i] + digit + prime_str[i+1:]) if new_num >= 1000 and new_num in primes: adj_list[prime].append(new_num) return adj_list
def bfs_shortest_path(adj_list, start, end): from collections import deque queue = deque([(start, 0)]) visited = set([start]) while queue: current, steps = queue.popleft() if current == end: return steps for neighbor in adj_list[current]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, steps + 1)) return -1
def main(): import sys input = sys.stdin.read data = input().split() A = int(data[0]) B = int(data[1])
primes = sieve_of_eratosthenes(9999)
adj_list = build_adjacency_list(primes)
result = bfs_shortest_path(adj_list, A, B)
print(result)if name == "main": main()
解释：
- sieve_of_eratosthenes：生成1000到9999之间的所有质数。
- build_adjacency_list：构建质数之间的邻接表。
- bfs_shortest_path：使用BFS找到从A到B的最短路径。
- main：读取输入，调用函数，输出结果。
注意事项：
- 确保输入的A和B都是四位数质数。
- 处理边界情况，如A和B相同的情况。
通过上述步骤和代码，可以有效地解决Prime Path问题。
发表回复