Leetcode 3609. Minimum Moves to Reach Target in Grid

• Leetcode 3609. Minimum Moves to Reach Target in Grid
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3609. Minimum Moves to Reach Target in Grid

1. 解题思路

这一题我一开始走岔了，走了一个正向遍历走法的思路，无论怎么剪枝都一直超时。后来看了一下答案之后发现，这道题核心是倒推，而且事实上根据结果点的状态，走法事实上是唯一的。

下面，我们就来考察一下具体的走法。

假设当前的点为$(x,y)$，其有三种状态：

1. $x<y$
2. $x>y$
3. $x=y$

显然，其对应的走法一共有六种，且走完之后的新坐标 x ′ , y ′ x\', y\' x′,y′的关系如下：

1. $x<y$
   • x ′ = x + y x\'=x+y x′=x+y， y ′ = y y\'=y y′=y，此时有 y ′ < x ′ < 2 y ′ y\' < x\' < 2y\' y′<x′<2y′
   • x ′ = x x\'=x x′=x， y ′ = x + y y\'=x+y y′=x+y，此时有 y ′ > 2 x ′ y\' > 2x\' y′>2x′
2. $x>y$
   • x ′ = x + y x\'=x+y x′=x+y， y ′ = y y\'=y y′=y，此时有 x ′ > 2 y ′ x\' > 2y\' x′>2y′
   • x ′ = x x\'=x x′=x， y ′ = x + y y\'=x+y y′=x+y，此时有 x ′ < y ′ < 2 x ′ x\' < y\' < 2x\' x′<y′<2x′
3. $x=y$
   • x ′ = x + y x\'=x+y x′=x+y， y ′ = y y\'=y y′=y，此时有 x ′ = 2 y ′ x\' = 2y\' x′=2y′
   • x ′ = x x\'=x x′=x， y ′ = x + y y\'=x+y y′=x+y，此时有 y ′ = 2 x ′ y\' = 2x\' y′=2x′

由此，我们根据当前的位置 ( x ′ , y ′ ) (x\', y\') (x′,y′)，必然可以唯一地推导出上一步的位置$(x,y)$。

然后我们只需要倒推看看能否回到$(sx,sy)$点即可。

2. 代码实现

给出python代码实现如下：

class Solution: def minMoves(self, sx: int, sy: int, tx: int, ty: int) -> int: if sx == 0 and sy == 0: return 0 if tx == 0 and ty == 0 else -1 ans = 0 while tx >= sx and ty >= sy: if tx == sx and ty == sy: return ans if ty == tx: if sx > 0 and sy > 0:  return -1 if sx == 0:  tx -= ty else:  ty -= tx elif tx >= 2 * ty: if tx % 2 == 1:  return -1 tx = tx // 2 elif ty < tx < 2 * ty: tx -= ty elif tx < ty < 2 * tx: ty = ty - tx elif ty >= 2 * tx: if ty % 2 == 1:  return -1 ty = ty // 2 ans += 1 return ans if tx == sx and ty == sy else -1

提交代码评测得到：耗时3ms，占用内存17.61MB。