3609. Minimum Moves to Reach Target in Grid Hard

1/**
2 * [3609] Minimum Moves to Reach Target in Grid
3 *
4 * You are given four integers sx, sy, tx, and ty, representing two points (sx, sy) and (tx, ty) on an infinitely large 2D grid.
5 * You start at (sx, sy).
6 * At any point (x, y), define m = max(x, y). You can either:
7 * 
8 * 	Move to (x + m, y), or
9 * 	Move to (x, y + m).
10 * 
11 * Return the minimum number of moves required to reach (tx, ty). If it is impossible to reach the target, return -1.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">sx = 1, sy = 2, tx = 5, ty = 4</span>
16 * Output: <span class="example-io">2</span>
17 * Explanation:
18 * The optimal path is:
19 * 
20 * 	Move 1: max(1, 2) = 2. Increase the y-coordinate by 2, moving from (1, 2) to (1, 2 + 2) = (1, 4).
21 * 	Move 2: max(1, 4) = 4. Increase the x-coordinate by 4, moving from (1, 4) to (1 + 4, 4) = (5, 4).
22 * 
23 * Thus, the minimum number of moves to reach (5, 4) is 2.
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">sx = 0, sy = 1, tx = 2, ty = 3</span>
28 * Output: <span class="example-io">3</span>
29 * Explanation:
30 * The optimal path is:
31 * 
32 * 	Move 1: max(0, 1) = 1. Increase the x-coordinate by 1, moving from (0, 1) to (0 + 1, 1) = (1, 1).
33 * 	Move 2: max(1, 1) = 1. Increase the x-coordinate by 1, moving from (1, 1) to (1 + 1, 1) = (2, 1).
34 * 	Move 3: max(2, 1) = 2. Increase the y-coordinate by 2, moving from (2, 1) to (2, 1 + 2) = (2, 3).
35 * 
36 * Thus, the minimum number of moves to reach (2, 3) is 3.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">sx = 1, sy = 1, tx = 2, ty = 2</span>
41 * Output: <span class="example-io">-1</span>
42 * Explanation:
43 * 
44 * 	It is impossible to reach (2, 2) from (1, 1) using the allowed moves. Thus, the answer is -1.
45 * </div>
46 *  
47 * Constraints:
48 * 
49 * 	0 <= sx <= tx <= 10^9
50 * 	0 <= sy <= ty <= 10^9
51 * 
52 */
53pub struct Solution {}
54
55// problem: https://leetcode.com/problems/minimum-moves-to-reach-target-in-grid/
56// discuss: https://leetcode.com/problems/minimum-moves-to-reach-target-in-grid/discuss/?currentPage=1&orderBy=most_votes&query=
57
58// submission codes start here
59
60impl Solution {
61    pub fn min_moves(sx: i32, sy: i32, tx: i32, ty: i32) -> i32 {
62        0
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_3609() {
74    }
75}
76