题意
在2D平面上给出n
个整数点points
, points[i] = [xi, yi]
, xi
、yi
都是整数,访问所有points
需要多少秒?
其中:
- 水平移动一个单元、垂直移动一个单元、对角移动一个单元(水平移动一次、垂直移动一次)都认为只耗时1秒;
- 只能顺序访问
points
;
解法
拿到题目后核心需要解决从A点到B点需要多少秒,知道AB两点需要多少秒后,后面只需要遍历points
重复计算即可。
A、B点可以形成两种类型的矩形,瘦矩形和胖矩形,由于对角移动只耗时1秒(相当于移动了两次一次水平一次垂直,优于直接进行水平移动和垂直移动),所以A到B点优先对角移动,使对角移动最大化,然后再水平或者垂直移动。
- 针对瘦矩形 (
|x2-x1| < |y2-y1|
)
从A点(1,1)
到B点(3,6)
最优耗时计算:先对角移动在垂直移动(1,1)->(3,3)->(3,6)
瘦矩阵移动耗时移动路径(x1,y1)->(x2,x2)->(x2,y2)
通用计算:|x2-x1|+(|y2-y1|-|x2-x1|)
- 针对胖矩形 (
|x2-x1|>|y2-y1|
)
从A点(1,1)
到B点(6,3)
最优耗时计算:先对角移动在垂直移动(1,1)->(3,3)->(6,3)
瘦矩阵移动耗时移动路径(x1,y1)->(y2,y2)->(x2,y2)
通用计算:|y2-y1|+(|x2-x1|-|y2-y1|)
结合胖矩阵和瘦矩阵,最后A(x1, y1)
点到B(x2, y2)
点的耗时为:
综合得
代码
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int sum = 0;
for (size_t i = 1; i < points.size(); ++ i) {
int xt = abs(points[i][0]-points[i-1][0]);
int yt = abs(points[i][1]-points[i-1][1]);
sum += min(xt, yt) + abs(yt-xt);
}
return sum;
}
};
网友评论