二维整数列表相邻元素公因子校验及X-Y连通路径查找代码问题求助

原代码核心问题 #

• 坐标逻辑错误：双重循环i/j的取值和当前所在位置完全无关，没有基于当前坐标判断相邻格子，导致会校验非相邻元素
• 公约数判断逻辑错误：1和任何数的最大公约数都是1，不满足规则要求，原代码反而判定num1==1时存在有效公约数；且遍历找公约数效率极低，可直接用最大公约数判断
• 重复访问判断逻辑错误：仅判断数值是否在路径中，若网格存在重复数值会误判，应该基于坐标判断是否访问过；且checkList函数实现冗余，循环逻辑完全无效
• 搜索逻辑缺陷：既不是深度优先也不是广度优先，属于贪心走法，很容易进入死路无法找到连通路径

修正后实现 #

我们采用广度优先搜索（BFS）来查找最短连通路径，仅允许移动到上下左右四个方向的相邻格子，移动规则为两个格子数值的最大公约数大于1。

import math
from collections import deque

# 构建网格，X的坐标为(2,2)，Y的坐标为(5,5)，可根据实际数值替换占位
grid = [
    [92, 78, 39, 38, 95, 19, 57, 72],
    [90, 61, 26, 51, 78, 41, 82, 27],
    [99, 9, 0, 17, 87, 40, 42, 12],  # 0为X的占位，可替换为X的实际数值
    [20, 62, 31, 33, 54, 5, 74, 75],
    [34, 35, 77, 11, 25, 10, 37, 81],
    [85, 91, 45, 18, 43, 1, 15, 36], # 1为Y的占位，可替换为Y的实际数值
    [93, 13, 65, 63, 21, 49, 60, 58],
    [84, 69, 66, 70, 55, 30, 24, 29]
]

# 上下左右四个移动方向
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 起点X坐标，终点Y坐标
start = (2, 2)
end = (5, 5)
# 记录访问过的坐标避免重复遍历
visited = set()
visited.add(start)
# BFS队列，每个元素存储(当前坐标, 当前路径数值列表)
q = deque()
q.append((start, [grid[start[0]][start[1]]]))

found = False
while q:
    (x, y), path = q.popleft()
    # 到达终点，输出路径
    if (x, y) == end:
        print("找到连通路径：", path)
        found = True
        break
    # 遍历四个相邻方向
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        # 校验坐标在网格范围内
        if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
            if (nx, ny) not in visited:
                current_val = grid[x][y]
                next_val = grid[nx][ny]
                # 判断是否存在大于1的公约数
                if math.gcd(current_val, next_val) > 1:
                    visited.add((nx, ny))
                    q.append(((nx, ny), path + [next_val]))

if not found:
    print("不存在符合规则的连通路径")

内容的提问来源于stack exchange，提问作者Rody