Python 程序检查一个点是否可以转换为另一个点

假设我们有一个起点 (sx, sy) 和一个目标点 (tx, ty)，我们需要检查是否存在从起点到终点的移动序列。这里的移动包括取一个点 (x, y) 并将其转换为 (x, x+y) 或 (x+y, y)。

所以，如果输入类似于 (sx, sy) = (1,1) (tx, ty) = (4,5)，则输出将为 True，这是因为可以将 (1,1) 移动到 (2,1)，然后 (3,1)，然后 (4,1)，然后 (4,5)。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 solve()。它将接收 sx、sy、tx、ty 作为参数。

  • 如果 sx > tx 或 sy > ty，则

    • 返回 False

  • 如果 sx 等于 tx，则

    • 返回 (ty-sy) 对 sx 取模是否等于 0

  • 如果 sy 等于 ty，则

    • 返回 (tx - sx) 对 sy 取模是否等于 0

  • 返回 solve(sx, sy, tx-ty, ty) 或 solve(sx, sy, tx, ty-tx)

示例

让我们看看下面的实现以更好地理解。

def solve(sx, sy, tx, ty):
   if sx > tx or sy > ty:
      return False
   if sx == tx:
      return (ty-sy)%sx == 0
   if sy == ty:
      return (tx - sx)%sy == 0
   return solve(sx, sy, tx-ty, ty) or solve(sx, sy, tx, ty-tx)

(sx, sy) = (1,1)
(tx, ty) = (4,5)
print(solve(sx, sy, tx, ty))

输入

(1,1), (4,5)

输出

True

更新于: 2021年10月8日

95 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告