h****n
发帖数: 1093 | 1 REACH
You are in an infinite 2D grid where you can move in any of the 8 directions
:
(x,y) to
(x+1, y),
(x - 1, y),
(x, y+1),
(x, y-1),
(x-1, y-1),
(x+1,y+1),
(x-1,y+1),
(x+1,y-1)
You are given a sequence of points and the order in which you need to cover
the points. Give the minimum number of steps in which you can achieve it.
You start from the first point.
Example :
Input : [(0, 0), (1, 1), (1, 2)]
Output : 2
It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to
move from (1, 1) to (1, 2).
This question is intentionally left slightly vague. Clarify the question by
trying out a few cases in the “See Expected Output” section. | z*********8
发帖数: 2070 | | s*******n
发帖数: 163 | 3 是严格按照input中的点的顺序吗？如果是，那这题很容易。
难道有隐藏的难点我没看出来？ | m****s
发帖数: 1481 | 4 如果是按照一定的顺序，那可能需要避开排在后面但是在最短路径上的点?
同样道理需要检验会不会在reach一个点之前被后面的点包围了 | u******e
发帖数: 758 | 5 我的想法是算所有点距C(n,2) O(N^2)，全排列求最小和O(N!) | a********5
发帖数: 1631 | 6 说老实话，没太看懂这道题
给定的点集顺序都是固定的，相邻两点之间计算步数是O（1），那应该就是过一遍所有
点集就行？如果这样为什么还要问“min step"？难道不是应该只有一个唯一答案？
还是说前面已经走过的点，后面如果再出现可以直接跳过，每个点只要走一遍？但是题
目里好像不是这个意思啊 |
|
