Thời gian tối thiểu thăm tất cả điểm trong C++

Cho mảng điểm 2D, tìm thời gian tối thiểu (giây) để thăm tất cả điểm theo thứ tự. Mỗi giây di chuyển được: ngang, dọc, hoặc chéo (1 đơn vị).

Ví dụ

Points: (1,1) → (3,4) → (-1,0)

Thời gian: max(|3-1|, |4-1|) + max(|-1-3|, |0-4|) = max(2,3) + max(4,4) = 3 + 4 = 7

Thuật toán

Thời gian từ (x1,y1) đến (x2,y2) = max(|x2-x1|, |y2-y1|) (di chuyển chéo kết hợp ngang/dọc). Tổng thời gian = tổng các cặp liên tiếp.

Chương trình mẫu

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& p) {
        int ans = 0;
        int n = p.size();
        for (int i = 1; i < n; i++) {
            int dx = abs(p[i][0] - p[i-1][0]);
            int dy = abs(p[i][1] - p[i-1][1]);
            ans += max(dx, dy);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> c = {{1,1}, {3,4}, {-1,0}};
    cout << ob.minTimeToVisitAllPoints(c);
    return 0;
}

Kết quả

7

Giải thích: Di chuyển chéo giảm cả dx và dy cùng lúc. Số bước = max(dx, dy). Ví dụ (1,1)→(3,4): dx=2, dy=3 → 3 bước chéo (giảm cả 2) + 1 bước dọc = 3 bước.

Độ phức tạp: O(n) thời gian, O(1) không gian.