仅使用对角线移动到达目的地的最小成本
Min Cost to reach destination using only diagonal moves
给定一个无限网格，我们需要找出从给定源到达目的地所需的最低成本。成本计算如下。
只允许对角线移动。
只有当方向改变时成本才会增加。类似于象棋中的象棋。您可以根据需要在同一对角线上移动任意数量的单元格，而不会产生任何额外费用。如果源为 (1,1) 且目标为 (3,3)，则成本为 1.
谁能帮我用高效的算法来实现这个。
你可以从任何地方到达任何地方，方向改变不超过 1 次。因此，如果源和目标在同一条对角线上，则成本为零。否则成本为 1.
查找实际路径：
Let source be at xs, ys
Let destination be xd, yd
Specify four diagonal lines passing through the points
y = ys + ( xs - x )
y = ys - ( xs - x )
Is destination on one of these lines? If so, done.
y = yd + ( xd - x )
y = yd - ( xd - x )
Calculate line intersection ( https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection )
There will be two - select one
Travel from source to intersection point
Travel from intersection to destination
给定一个无限网格，我们需要找出从给定源到达目的地所需的最低成本。成本计算如下。 只允许对角线移动。 只有当方向改变时成本才会增加。类似于象棋中的象棋。您可以根据需要在同一对角线上移动任意数量的单元格，而不会产生任何额外费用。如果源为 (1,1) 且目标为 (3,3)，则成本为 1.
谁能帮我用高效的算法来实现这个。
你可以从任何地方到达任何地方，方向改变不超过 1 次。因此，如果源和目标在同一条对角线上，则成本为零。否则成本为 1.
查找实际路径：
Let source be at xs, ys
Let destination be xd, yd
Specify four diagonal lines passing through the points
y = ys + ( xs - x )
y = ys - ( xs - x )
Is destination on one of these lines? If so, done.
y = yd + ( xd - x )
y = yd - ( xd - x )
Calculate line intersection ( https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection )
There will be two - select one
Travel from source to intersection point
Travel from intersection to destination