根据搜索结果,对于 LeetCode 3609 题,目前公开的 Rust 解法信息比较有限。不过我找到了思路相近的题解,可以为你提供实现参考。

3609 题的核心通常是使用逆向思维 + 贪心/模拟,从终点倒推到起点。这里参考类似问题的 C++ 解法逻辑,提供一个 Rust 版本的实现思路:

```rust
impl Solution {
    pub fn min_moves(sx: i32, sy: i32, tx: i32, ty: i32) -> i32 {
        let mut x = tx;
        let mut y = ty;
        let mut moves = 0;

        while x > sx || y > sy {
            if x < sx || y < sy {
                return -1;
            }

            if x > y {
                if x <= 2 * y {
                    x -= y;
                } else {
                    if x % 2 == 1 {
                        return -1;
                    }
                    x /= 2;
                }
            } else if y > x {
                if y <= 2 * x {
                    y -= x;
                } else {
                    if y % 2 == 1 {
                        return -1;
                    }
                    y /= 2;
                }
            } else { // x == y
                if sx > 0 {
                    y = 0;
                } else {
                    x = 0;
                }
            }
            moves += 1;
        }

        if x == sx && y == sy {
            moves
        } else {
            -1
        }
    }
}
```

💡 思路说明

· 逆向推导:从终点 (tx, ty) 倒推回起点 (sx, sy),因为正推分支太多,倒推时每一步的操作通常是唯一的。
· 贪心策略:倒推时,较大的坐标来自上一步的“加倍”操作。如果 x > y,说明上一步对 x 做了操作,根据 x 和 y 的大小关系决定是回退 x -= y 还是 x /= 2(必须确保 x 是偶数)。y > x 时同理。
· 相等特判:当 x == y 且尚未到达起点时,需要根据起点坐标决定让哪个坐标归零,以继续倒推。

💎 复杂度分析

这个实现的时间复杂度约为 O(log(max(tx, ty))),因为每次循环坐标至少减半或减少,效率很高。

如果这个思路和题目描述有出入,你可以提供具体的移动规则,我能再帮你调整实现。

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐