LeetCode：1266. Minimum Time Visiting All Points访问所有点的最小时间（C语言）

忘是亡心i 2022-12-31 03:24 97阅读 0赞

**题目描述：**  
平面上有 n 个点，点的位置用整数坐标表示 points\[i\] = \[xi, yi\]。请你计算访问所有这些点需要的最小时间（以秒为单位）。

你可以按照下面的规则在平面上移动：

每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
    必须按照数组中出现的顺序来访问这些点。

示例 1：  
![在这里插入图片描述][72fab3f71ee3d0a6090cddd33902ba48.png_pic_center]

输入：points = \[\[1,1\],\[3,4\],\[-1,0\]\]  
输出：7  
解释：一条最佳的访问路径是： \[1,1\] -> \[2,2\] -> \[3,3\] -> \[3,4\] -> \[2,3\] -> \[1,2\] -> \[0,1\] -> \[-1,0\]  
从 \[1,1\] 到 \[3,4\] 需要 3 秒  
从 \[3,4\] 到 \[-1,0\] 需要 4 秒  
一共需要 7 秒

示例 2：

输入：points = \[\[3,2\],\[-2,2\]\]  
输出：5

提示：

points.length == n
    1 <= n <= 100
    points[i].length == 2
    -1000 <= points[i][0], points[i][1] <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-time-visiting-all-points  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

//#define abs(x) ((x) > 0 ? (x) : (0 - x))
    
    int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){ 
        int res = 0;
        int i = 0;
        int xoffset = 0;
        int yoffset = 0;
    
        for(i = 1; i < pointsSize;i++){ 
            xoffset = abs(points[i][0] - points[i - 1][0]); //x
            yoffset = abs(points[i][1] - points[i - 1][1]); //y
    
            //切比雪夫距离
            if(xoffset < yoffset){ 
                res += yoffset;
            }
            else{ 
                res += xoffset;
            }
        }
    
        return res;
    }

**运行结果：**  
![在这里插入图片描述][20201228101744831.png_pic_center]**Notes：**  
x移动到y最少次数为dx（|x0-x1|），dy（|y0-y1|）中较大值max（dx，dy）称为切比雪夫距离。

[72fab3f71ee3d0a6090cddd33902ba48.png_pic_center]: /images/20221120/cd79b64174b24c40b9090fe73a9ad045.png
[20201228101744831.png_pic_center]: /images/20221120/e32ef938968d449e8790a5c2b5bbbc28.png