Thời gian tối thiểu để truy cập tất cả các điểm trong C ++

Giả sử có một số điểm đã cho dưới dạng một mảng. Chúng ta phải tìm thời gian tối thiểu tính bằng giây để tham quan tất cả các điểm. Có một số điều kiện.

• Trong một giây, nó có thể di chuyển theo chiều dọc, ngang và chéo
• Chúng tôi phải truy cập các điểm theo thứ tự giống như chúng xuất hiện trong mảng.

Vì vậy, nếu các điểm là [(1, 1), (3, 4), (-1, 0)], thì đầu ra sẽ là 7. Nếu chúng ta kiểm tra trình tự cho tuyến đường ngắn nhất, chuỗi sẽ là (1, 1 ), (2, 2), (3, 3), (3, 4), (2, 3), (1, 2), (0, 1), (-1, 0)

Để giải quyết điều này, chúng ta sẽ chỉ tìm hiệu số lớn nhất của hiệu số x của hai điểm liên tiếp và hiệu số toạ độ y của hai điểm liên tiếp. Các giá trị tối đa sẽ được cộng lại với nhau.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[[1,1],[3,4],[-1,0]]

Đầu ra

7