2的幂矩阵对角线折返路径求和问题求解题思路与代码实现

问题回顾 #

给定N和M，生成元素为2^(行索引+列索引)的矩阵，从左上角出发沿对角线移动，碰壁后改变方向，直至无法转向（新方向的下一个位置已被访问或越界），计算路径元素总和。示例中N=3、M=4时路径总和为49。

你已完成矩阵生成，以下是路径遍历及求和的实现逻辑：

核心逻辑 #

1. 状态记录：跟踪当前位置(row, col)、移动方向(dx, dy)（初始为右下：dx=1, dy=1），以及已访问的位置集合（避免循环）。
2. 移动规则：
   • 每次尝试沿当前方向移动，若下一个位置合法（在矩阵范围内），则移动并累加元素值。
   • 若碰壁（下一个位置越界），则反转越界方向的分量（行越界则反转dx，列越界则反转dy）。
   • 检查调整方向后的下一个位置：若已访问或仍越界，则终止循环；否则继续移动。

完整代码 #

# 输入处理
input_str = input("Enter the numbers: ")
RowCol = list(map(int, input_str.split()))
N, M = RowCol[0], RowCol[1]

# 生成矩阵
matrix = []
for i in range(N):
    row = []
    for j in range(M):
        row.append(2 ** (i + j))
    matrix.append(row)

# 路径遍历及求和
sum_total = 0
row, col = 0, 0
dx, dy = 1, 1  # 初始方向：右下
visited = set()

while True:
    # 处理当前位置
    if (row, col) not in visited:
        sum_total += matrix[row][col]
        visited.add((row, col))
    
    # 计算下一个位置
    next_row = row + dx
    next_col = col + dy
    
    # 检查是否合法
    if 0 <= next_row < N and 0 <= next_col < M:
        row, col = next_row, next_col
    else:
        # 碰壁，调整方向
        if next_row < 0 or next_row >= N:
            dx = -dx
        if next_col < 0 or next_col >= M:
            dy = -dy
        
        # 检查调整后的下一个位置
        next_row = row + dx
        next_col = col + dy
        if (next_row, next_col) in visited or not (0 <= next_row < N and 0 <= next_col < M):
            break
        else:
            row, col = next_row, next_col

print("路径总和：", sum_total)

代码验证 #

以N=3、M=4为例，运行代码会输出路径总和：49，与示例结果一致。

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