• 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^{\prime },y^{\prime }$的关系如下：

1. $x<y$
   • $x^{\prime }=x+y$，$y^{\prime }=y$，此时有$y^{\prime }<x^{\prime }<2y^{\prime }$
   • $x^{\prime }=x$，$y^{\prime }=x+y$，此时有$y^{\prime }>2x^{\prime }$
2. $x>y$
   • $x^{\prime }=x+y$，$y^{\prime }=y$，此时有$x^{\prime }>2y^{\prime }$
   • $x^{\prime }=x$，$y^{\prime }=x+y$，此时有$x^{\prime }<y^{\prime }<2x^{\prime }$
3. $x=y$
   • $x^{\prime }=x+y$，$y^{\prime }=y$，此时有$x^{\prime }=2y^{\prime }$
   • $x^{\prime }=x$，$y^{\prime }=x+y$，此时有$y^{\prime }=2x^{\prime }$

由此，我们根据当前的位置$(x^{\prime },y^{\prime })$，必然可以唯一地推导出上一步的位置$(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 -1ans = 0while tx >= sx and ty >= sy:if tx == sx and ty == sy:return ansif ty == tx:if sx > 0 and sy > 0:return -1if sx == 0:tx -= tyelse:ty -= txelif tx >= 2 * ty:if tx % 2 == 1:return -1tx = tx // 2elif ty < tx < 2 * ty:tx -= tyelif tx < ty < 2 * tx:ty = ty - txelif ty >= 2 * tx:if ty % 2 == 1:return -1ty = ty // 2ans += 1return ans if tx == sx and ty == sy else -1

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