ปัญหา
ได้รับจุดหลายจุดเป็นอาร์เรย์ หาเวลาน้อยที่สุด (วินาที) ในการเยี่ยมชมจุดทั้งหมด เงื่อนไข:
- 1 วินาที เคลื่อนที่ได้: แนวตั้ง, แนวนอน, แนวทแยง
- ต้องเยี่ยมชมตามลำดับในอาร์เรย์
เช่น Points = [(1,1), (3,4), (-1,0)] → Output = 7 เส้นทาง: (1,1)→(2,2)→(3,3)→(3,4)→(2,3)→(1,2)→(0,1)→(-1,0)
วิธีแก้
หา Max ของ |x2-x1| และ |y2-y1| ระหว่างจุดติดกัน รวม Max ทั้งหมด
ตัวอย่างโค้ด
#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++) {
ans += max(abs(p[i][0] - p[i-1][0]), abs(p[i][1] - p[i-1][1]));
}
return ans;
}
};
int main() {
Solution ob;
vector<vector<int>> c = {{1,1}, {3,4}, {-1,0}};
cout << ob.minTimeToVisitAllPoints(c);
}
อินพุต
[[1,1],[3,4],[-1,0]]
เอาต์พุต
7
คำอธิบาย
การเคลื่อนที่แบบ Chebyshev Distance: ระยะทาง = max(|Δx|, |Δy|) เพราะเคลื่อนที่ทแยงได้ครอบคลุมทั้ง x และ y พร้อมกัน
จุด (1,1)→(3,4): Δx=2, Δy=3 → max=3
จุด (3,4)→(-1,0): Δx=4, Δy=4 → max=4
รวม = 3+4 = 7
