Cross a Three-Lane Road with Few Side Jumps

### Problem At point zero on a three-lane road, a frog starts in lane 2. `obstacles[i]` is zero for no obstacle or names the one blocked lane at point i. Moving to the next point in the same lane costs no side jump if the destination is clear. At one point the frog may jump directly to any other clear lane, including from lane 1 to lane 3. Return the minimum side jumps to reach the final point in any lane. ```cpp class Solution { public: int minSideJumps(vector<int>& obstacles); }; ``` ### Examples **Example 1:** ```text obstacles = [0,2,0] Output: 1 Explanation: Leave lane 2 at point zero, then move forward in another lane. ``` **Example 2:** ```text obstacles = [0,1,2,0] Output: 1 Explanation: Travel to point 1 in lane 2, jump to lane 3, and finish. ``` ### Constraints - `obstacles.length == n+1`, with `1 <= n <= 5*10^5`. - `0 <= obstacles[i] <= 3`. - The first and last entries are zero; each point has at most one blocked lane. ### Clarifying Questions A side jump keeps the same point coordinate and costs one even between the two outer lanes. Forward moves cannot pass through a blocked destination. ```hint Inspect the structure Which moves are free, and can a same-point side jump land in a blocked lane? ``` ### Reasoning checkpoints - Account for free forward moves, legal same-point side jumps, and the initial middle lane. - Prove the minimum number of side jumps while excluding every blocked landing. ### Optional extensions How would adding different costs for each lane-to-lane jump change the three-state closure?