• 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。