Python实现无固定起止点的0-1矩阵最长1路径求解方法

问题说明 #

我们需要在仅由0和1组成的矩阵中，寻找最长的全1可通行路径，规则如下：

• 路径无固定起点和终点
• 路径中的每个1仅可被访问一次
• 默认仅支持上下左右四个方向移动（四连通规则）

核心实现思路 #

• 采用回溯+深度优先搜索(DFS) 遍历所有可能的路径：通过回溯机制保证单条路径的节点不会重复计数，同时不会影响其他路径的搜索
• 无需额外的访问标记矩阵：直接修改原矩阵中当前访问的1为0，回溯时恢复为1即可，节省内存开销
• 遍历矩阵中所有值为1的单元格作为路径起点，保证不会遗漏任何可能的最长路径

完整Python代码 #

def longest_one_path(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    max_length = 0
    # 四连通方向，如需支持八连通可新增(1,1),(1,-1),(-1,1),(-1,-1)四个方向
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(x, y, current_len):
        nonlocal max_length
        # 更新全局最长路径长度
        if current_len > max_length:
            max_length = current_len
        # 遍历所有可移动方向
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            # 边界校验+是否可通行校验
            if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] == 1:
                # 标记当前节点为已访问
                matrix[nx][ny] = 0
                dfs(nx, ny, current_len + 1)
                # 回溯恢复节点状态
                matrix[nx][ny] = 1
    
    # 遍历所有1作为路径起点
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 1:
                matrix[i][j] = 0
                dfs(i, j, 1)
                matrix[i][j] = 1
    return max_length

示例测试 #

示例1测试 #

输入矩阵：

1 0 0 1
1 0 0 1
1 1 1 1
0 1 0 1

测试代码：

matrix1 = [
    [1,0,0,1],
    [1,0,0,1],
    [1,1,1,1],
    [0,1,0,1]
]
print(longest_one_path(matrix1))
# 输出结果：8，和预期一致

示例2测试 #

输入矩阵：

0 0 0 1
1 1 0 0
0 1 0 0
1 1 1 1

测试代码：

matrix2 = [
    [0,0,0,1],
    [1,1,0,0],
    [0,1,0,0],
    [1,1,1,1]
]
print(longest_one_path(matrix2))
# 输出结果：6，和预期一致

注意事项 #

上述方案为暴力搜索实现，适合小规模矩阵使用。如果矩阵规模超过10x10，可结合记忆化搜索或动态规划进一步优化性能。

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