algorithm - 仅使用对角线移动到达目的地的最低成本
问题描述
给定一个无限网格,我们需要找出从给定源到达目的地所需的最低成本。费用计算如下。只允许对角线移动。只有当方向改变时,成本才会增加。类似于象棋中的主教移动。您可以根据需要在同一对角线上移动任意数量的单元格,而不会产生任何额外费用。如果源是 (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
推荐阅读
- javascript - 通过使用 createdAt 与 Parse 服务器进行聚合不起作用
- c# - Wpf 应用程序冻结 - 大量内存泄漏难题
- postgresql - Postgres 选择带有偏移量的大表查询需要太多时间来处理
- php - 在不公开的情况下访问 PDF
- mongodb - 在 Elixir 中启动 2 个 MongoDB 连接
- linux - 用于管理多个作业的 cron/周期性构建的 Jenkins 插件?
- asp.net-core - 如何删除消息“您正在使用 .NET Core SDK 的预览版”
- php - PHP - 用正确的 Unicode 符号替换 JSON
- c# - Visual Studio For Mac .net Core 2.0 Ajax 将模型传递给控制器
- c++ - 使 C++14 constexpr 函数与 C++11 兼容