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]]