C++ 中访问所有点的最短时间

假设已给定一个数组中的一些点。我们必须找到秒数内所有点的访问的最短时间。有以下一些条件。

• 在一秒内，它可以垂直、水平和对角移动
• 我们必须按它们在阵列中出现的顺序访问这些点。

因此，如果这些点是 [(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

Arnab Chakraborty

更新于: 2020年4月29日

173 次浏览

开启你的 事业

完成课程以获得认证

开始