แอร์เมสส่งจดหมาย: หลังส่งแต่ละฉบับ ตำแหน่งเหลือเลขที่ต้องจำแค่ตัวเดียว

#include <bits/stdc++.h>
using namespace std;
const int OFF = 1000, W = 2001, INF = 1e9;
// row[c] = ระยะน้อยสุด ถ้าตอนนี้ยืนบนถนนแนวนอนของฉบับล่าสุด ที่ x = c - OFF
// col[c] = ระยะน้อยสุด ถ้าตอนนี้ยืนบนถนนแนวตั้งของฉบับล่าสุด ที่ y = c - OFF
int row[W], col[W];
int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    fill(row, row + W, INF); fill(col, col + W, INF);
    row[OFF] = col[OFF] = 0;    // จุดเริ่ม (0,0) นับเป็นฉบับที่ 0 ยืนอยู่บนทั้งสองเส้นของมัน
    int px = 0, py = 0;           // พิกัดของฉบับก่อนหน้า
    for(int i = 0; i < n; i++){
        int x, y; scanf("%d %d", &x, &y);
        // ทางเลี้ยว หาไว้ก่อนจากแถวเก่า
        // toRow: จากถนนแนวตั้งเก่า เดินขึ้นลงไปชนถนนแนวนอนใหม่ y
        // toCol: จากถนนแนวนอนเก่า เดินซ้ายขวาไปชนถนนแนวตั้งใหม่ x
        int toRow = INF, toCol = INF;
        for(int c = 0; c < W; c++){
            if(col[c] < INF) toRow = min(toRow, col[c] + abs(c - OFF - y));
            if(row[c] < INF) toCol = min(toCol, row[c] + abs(c - OFF - x));
        }
        // ทางตรง อยู่ฝั่งเดิม เดินขนานไปเส้นใหม่ พิกัดอีกแกนไม่เปลี่ยน ช่องจึงเป็นช่องเดิม
        int dy = abs(py - y), dx = abs(px - x);
        for(int c = 0; c < W; c++){
            if(row[c] < INF) row[c] += dy;
            if(col[c] < INF) col[c] += dx;
        }
        // ทางเลี้ยวลงได้ช่องเดียวต่อฝั่ง: ถนนแนวนอนใหม่ที่ x = px กับถนนแนวตั้งใหม่ที่ y = py
        row[px + OFF] = min(row[px + OFF], toRow);
        col[py + OFF] = min(col[py + OFF], toCol);
        px = x; py = y;
    }
    int ans = INF;
    for(int c = 0; c < W; c++) ans = min({ans, row[c], col[c]});
    printf("%d\n", ans);
}

#include <bits/stdc++.h>
using namespace std;
const int OFF = 1000, W = 2001, INF = 1e9;
// ชุดย่อย N < 80: ยังไม่เชื่อว่าเดินไปจุดที่ใกล้ที่สุดพอ
// จากทุกสถานะ ลองไปยืนทุกจุดบนสองเส้นของฉบับถัดไป
int row[W], col[W], nrow[W], ncol[W];
int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    fill(row, row + W, INF); fill(col, col + W, INF);
    row[OFF] = col[OFF] = 0;
    int px = 0, py = 0;
    for(int i = 0; i < n; i++){
        int x, y; scanf("%d %d", &x, &y);
        fill(nrow, nrow + W, INF); fill(ncol, ncol + W, INF);
        for(int c = 0; c < W; c++){
            for(int s = 0; s < 2; s++){
                int d = s == 0 ? row[c] : col[c];
                if(d >= INF) continue;
                int cx = s == 0 ? c - OFF : px;   // ตำแหน่งจริงของสถานะนี้
                int cy = s == 0 ? py : c - OFF;
                for(int z = 0; z < W; z++){
                    nrow[z] = min(nrow[z], d + abs(cx - (z - OFF)) + abs(cy - y));   // ไปยืน (z, y)
                    ncol[z] = min(ncol[z], d + abs(cx - x) + abs(cy - (z - OFF)));   // ไปยืน (x, z)
                }
            }
        }
        copy(nrow, nrow + W, row); copy(ncol, ncol + W, col);
        px = x; py = y;
    }
    int ans = INF;
    for(int c = 0; c < W; c++) ans = min({ans, row[c], col[c]});
    printf("%d\n", ans);
}

// ตัวตรวจ เดินทีละก้าวบนตารางจริง ส่งจดหมายได้ฟรีเมื่อยืนแนวเดียวกับฉบับถัดไป
// ไม่ได้ใช้ข้ออ้างเรื่องถนนสองเส้นเลย สถานะคือ (ส่งไปแล้วกี่ฉบับ, x, y)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; scanf("%d", &n);
    vector<int> X(n), Y(n);
    int lo = 0, hi = 0;
    for(int i = 0; i < n; i++){
        scanf("%d %d", &X[i], &Y[i]);
        lo = min({lo, X[i], Y[i]}); hi = max({hi, X[i], Y[i]});
    }
    lo -= 2; hi += 2;                       // เผื่อขอบให้เดินอ้อมนอกกรอบได้
    int S = hi - lo + 1;
    auto id = [&](int k, int x, int y){ return (k * S + (x - lo)) * S + (y - lo); };
    vector<int> dist((n + 1) * S * S, INT_MAX);
    deque<array<int, 3>> dq;                // BFS แบบน้ำหนัก 0 กับ 1
    dist[id(0, 0, 0)] = 0; dq.push_back({0, 0, 0});
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    while(!dq.empty()){
        auto [k, x, y] = dq.front(); dq.pop_front();
        int d = dist[id(k, x, y)];
        if(k == n){ printf("%d\n", d); return 0; }
        if(x == X[k] || y == Y[k]){         // ส่งฉบับที่ k ตรงนี้ ไม่เสียระยะ
            int t = id(k + 1, x, y);
            if(dist[t] > d){ dist[t] = d; dq.push_front({k + 1, x, y}); }
        }
        for(int r = 0; r < 4; r++){
            int nx = x + dx[r], ny = y + dy[r];
            if(nx < lo || nx > hi || ny < lo || ny > hi) continue;
            int t = id(k, nx, ny);
            if(dist[t] > d + 1){ dist[t] = d + 1; dq.push_back({k, nx, ny}); }
        }
    }
}