1824. Minimum Sideway Jumps Medium

1/**
2 * [1824] Minimum Sideway Jumps
3 *
4 * There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second lane and wants to jump to point n. However, there could be obstacles along the way.
5 * You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point.
6 * 
7 * 	For example, if obstacles[2] == 1, then there is an obstacle on lane 1 at point 2.
8 * 
9 * The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.
10 * 
11 * 	For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.
12 * 
13 * Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.
14 * Note: There will be no obstacles on points 0 and n.
15 *  
16 * Example 1:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex1.png" style="width: 500px; height: 244px;" />
18 * Input: obstacles = [0,1,2,3,0]
19 * Output: 2 
20 * Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
21 * Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).
22 * 
23 * Example 2:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex2.png" style="width: 500px; height: 196px;" />
25 * Input: obstacles = [0,1,1,3,3,0]
26 * Output: 0
27 * Explanation: There are no obstacles on lane 2. No side jumps are required.
28 * 
29 * Example 3:
30 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex3.png" style="width: 500px; height: 196px;" />
31 * Input: obstacles = [0,2,1,0,3,0]
32 * Output: 2
33 * Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	obstacles.length == n + 1
39 * 	1 <= n <= 5 * 10^5
40 * 	0 <= obstacles[i] <= 3
41 * 	obstacles[0] == obstacles[n] == 0
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/minimum-sideway-jumps/
47// discuss: https://leetcode.com/problems/minimum-sideway-jumps/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn min_side_jumps(obstacles: Vec<i32>) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1824() {
65    }
66}
67