เวลาขั้นต่ำในการเยี่ยมชมทุกจุดใน C++

สมมติว่ามีบางจุดที่กำหนดเป็นอาร์เรย์ เราต้องหาเวลาขั้นต่ำเป็นวินาทีเพื่อเยี่ยมชมทุกจุด มีเงื่อนไขบางประการ

• ใน 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