題意
在2D平面上給出n個(gè)整數(shù)點(diǎn)points， points[i] = [xi, yi]饱狂， xi、yi都是整數(shù)宪彩，訪問(wèn)所有points需要多少秒休讳？
其中：
- 水平移動(dòng)一個(gè)單元、垂直移動(dòng)一個(gè)單元尿孔、對(duì)角移動(dòng)一個(gè)單元(水平移動(dòng)一次衍腥、垂直移動(dòng)一次)都認(rèn)為只耗時(shí)1秒磺樱；
- 只能順序訪問(wèn)
points;
解法
拿到題目后核心需要解決從A點(diǎn)到B點(diǎn)需要多少秒，知道AB兩點(diǎn)需要多少秒后婆咸，后面只需要遍歷points重復(fù)計(jì)算即可。
A芜辕、B點(diǎn)可以形成兩種類(lèi)型的矩形尚骄，瘦矩形和胖矩形，由于對(duì)角移動(dòng)只耗時(shí)1秒（相當(dāng)于移動(dòng)了兩次一次水平一次垂直侵续，優(yōu)于直接進(jìn)行水平移動(dòng)和垂直移動(dòng)）倔丈，所以A到B點(diǎn)優(yōu)先對(duì)角移動(dòng)，使對(duì)角移動(dòng)最大化状蜗，然后再水平或者垂直移動(dòng)需五。
- 針對(duì)瘦矩形 (
|x2-x1| < |y2-y1|)
從A點(diǎn)(1,1)到B點(diǎn)(3,6)最優(yōu)耗時(shí)計(jì)算：先對(duì)角移動(dòng)在垂直移動(dòng)(1,1)->(3,3)->(3,6)
瘦矩陣移動(dòng)耗時(shí)移動(dòng)路徑(x1,y1)->(x2,x2)->(x2,y2)
通用計(jì)算：|x2-x1|+(|y2-y1|-|x2-x1|)
- 針對(duì)胖矩形 (
|x2-x1|>|y2-y1|)
從A點(diǎn)(1,1)到B點(diǎn)(6,3)最優(yōu)耗時(shí)計(jì)算：先對(duì)角移動(dòng)在垂直移動(dòng)(1,1)->(3,3)->(6,3)
瘦矩陣移動(dòng)耗時(shí)移動(dòng)路徑(x1,y1)->(y2,y2)->(x2,y2)
通用計(jì)算：|y2-y1|+(|x2-x1|-|y2-y1|)
結(jié)合胖矩陣和瘦矩陣，最后A(x1, y1)點(diǎn)到B(x2, y2)點(diǎn)的耗時(shí)為：
綜合得
代碼
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;
}
};
