计算自定义3×3数字键盘输入字符串D所需的移动次数

核心思路 #

你不需要提前枚举所有45种数字组合，关键是先建立数字到键盘坐标的映射，然后利用切比雪夫距离计算任意两个数字间的移动次数——因为规则允许8方向移动（包括对角线），每一步可以同时改变行和列，所以移动次数等于两个坐标行差和列差的最大值。

具体步骤 #

1. 构建坐标映射表
   把输入的键盘字符串S按3×3网格拆分，每个字符对应的坐标为：

   • 索引idx对应的行号：idx // 3（取值0、1、2）
   • 索引idx对应的列号：idx % 3（取值0、1、2）
     比如S="918726534"时，数字1在索引1，坐标是(0,1)；数字5在索引6，坐标是(2,0)。

2. 计算总移动次数
   遍历数字字符串D，从第二个字符开始，依次计算当前字符与前一个字符的坐标差：

   • 行差绝对值：|x2 - x1|
   • 列差绝对值：|y2 - y1|
     移动次数取两者的最大值，累加到总次数中。

示例验证（对应题目中的例子） #

• 1→5：坐标(0,1)到(2,0)，行差2，列差1 → 取最大值2
• 5→2：坐标(2,0)到(1,1)，行差1，列差1 → 取最大值1
• 2→7：坐标(1,1)到(1,0)，行差0，列差1 → 取最大值1
• 7→3：坐标(1,0)到(2,1)，行差1，列差1 → 取最大值1
• 3→3：坐标相同，行差和列差均为0 → 加0
• 3→9：坐标(2,1)到(0,0)，行差2，列差1 → 取最大值2
  最终总和为2+1+1+1+0+2=7，与示例一致。

代码实现（Python） #

def calculate_movement(S, D):
    # 建立每个数字对应的键盘坐标映射
    num_to_pos = {}
    for idx, num_char in enumerate(S):
        row = idx // 3
        col = idx % 3
        num_to_pos[num_char] = (row, col)
    
    total_moves = 0
    if len(D) <= 1:
        return total_moves
    
    prev_row, prev_col = num_to_pos[D[0]]
    for curr_char in D[1:]:
        curr_row, curr_col = num_to_pos[curr_char]
        # 计算切比雪夫距离作为移动次数
        row_diff = abs(curr_row - prev_row)
        col_diff = abs(curr_col - prev_col)
        total_moves += max(row_diff, col_diff)
        prev_row, prev_col = curr_row, curr_col
    
    return total_moves

# 测试题目示例
S = "918726534"
D = "1527339"
print(calculate_movement(S, D))  # 输出7

为什么不用枚举组合？ #

实时计算坐标差的最大值比提前枚举所有组合更简洁，代码维护性更高——无论键盘布局S怎么变化，只需要重新生成坐标映射表即可，不需要修改核心计算逻辑。

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