สมมติว่ามีบางจุดที่กำหนดเป็นอาร์เรย์ เราต้องหาเวลาขั้นต่ำเป็นวินาทีเพื่อเยี่ยมชมทุกจุด มีเงื่อนไขบางประการ
- ใน 1 วินาที มันสามารถเคลื่อนที่ในแนวตั้ง แนวนอน และแนวทแยงมุมได้
- เราต้องไปที่จุดต่างๆ ในลำดับเดียวกันกับที่ปรากฏในอาร์เรย์
ดังนั้นหากจุดคือ [(1, 1), (3, 4), (-1, 0)] ดังนั้นเอาต์พุตจะเป็น 7 หากเราตรวจสอบลำดับสำหรับเส้นทางที่สั้นที่สุด ลำดับจะเป็น (1, 1 ), (2, 2), (3, 3), (3, 4), (2, 3), (1, 2), (0, 1), (-1, 0)
เพื่อแก้ปัญหานี้ เราจะต้องหาค่าความต่างพิกัด x สูงสุดของจุดสองจุดที่ต่อเนื่องกัน และค่าความต่างพิกัด y ของจุดสองจุดที่ต่อเนื่องกัน ค่าสูงสุดจะถูกรวมเข้าด้วยกัน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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; } }; main(){ Solution ob; vector<vector<int>> c = {{1,1},{3,4},{-1,0}}; cout << ob.minTimeToVisitAllPoints(c); }
อินพุต
[[1,1],[3,4],[-1,0]]
ผลลัพธ์
7