藍橋杯「移動距離」題解：矩陣蛇形編號座標映射與曼哈頓距離計算

題目復述

矩陣寬度為 w，編號從 1 起按「蛇形」排列：第一行左→右，第二行右→左，第三行左→右……已知兩樓號 m、n，求最短移動距離（只能上下左右，不能斜線），即曼哈頓距離。

核心洞察：編號轉座標

將 1-based 編號轉為 0-based 序號 idx = num - 1，則：

• 行號 r = idx / w（整除）
• 列號 c = idx % w（取模）
• 奇數行（r % 2 == 1）方向反轉，實際列 c' = w - 1 - c

參考代碼詳解

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int w, m, n;
    cin >> w >> m >> n;
    
    m--; n--;                    // 轉 0-based
    int r1 = m / w, c1 = m % w;
    int r2 = n / w, c2 = n % w;
    
    if (r1 & 1) c1 = w - 1 - c1; // 奇數行鏡像翻轉
    if (r2 & 1) c2 = w - 1 - c2;
    
    cout << abs(r1 - r2) + abs(c1 - c2) << endl; // 曼哈頓距離
    return 0;
}

逐步演示：樣例 w=6, m=8, n=2

另一樣例 w=4, m=7, n=20 驗證

矩陣（0-based 序號）：
 0  1  2  3
 7  6  5  4
 8  9 10 11
15 14 13 12
16 17 18 19
20 ...

m=7 → 序號6 → r=1,c=2 → 奇數行翻轉 c'=4-1-2=1 → (1,1)
n=20 → 序號19 → r=4,c=3 → 偶數行 c'=3 → (4,3)
距離 = |1-4| + |1-3| = 3 + 2 = 5 ✓

關鍵技巧總結

• 0-based 轉換：m--; n-- 統一座標系統，避免邊界困擾
• 位運算判奇偶：r & 1 比 r % 2 更快，嵌入式/競賽常用
• 鏡像翻轉公式：c' = w - 1 - c 將反向行映射回統一左→右坐標系
• 曼哈頓距離：網格無障礙移動最短路徑 = 行差絕對值 + 列差絕對值

擴展思考

• 若允許斜線移動（切比雪夫距離）：max(|r1-r2|, |c1-c2|)
• 若有障礙物：需 BFS/A* 搜索，不再是 O(1) 數學題
• 三維/高維推廣：同理座標映射後各維差值求和