1210. Minimum Moves to Reach Target with Rotations

In an `n*n` grid, there is a snake that spans 2 cells and starts moving from the top left corner at `(0, 0)` and `(0, 1)`. The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at `(n-1, n-2)` and `(n-1, n-1)`.

In one move the snake can:

• Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
• Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
• Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from `(r, c)` and `(r, c+1)` to `(r, c)` and `(r+1, c)`.
• Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from `(r, c)` and `(r+1, c)` to `(r, c)` and `(r, c+1)`.

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return `-1`.

Example 1:

```Input: grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].
```

Example 2:

```Input: grid = [[0,0,1,1,1,1],
[0,0,0,0,1,1],
[1,1,0,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,0]]
Output: 9
```

Constraints:

• `2 <= n <= 100`
• `0 <= grid[i][j] <= 1`
• It is guaranteed that the snake starts at empty cells.

1210. Minimum Moves to Reach Target with Rotations
``````struct Solution;

use std::collections::HashSet;
use std::collections::VecDeque;

type State = (usize, usize, bool);

impl Solution {
fn minimum_moves(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let mut visited: HashSet<State> = HashSet::new();
let start = (0, 0, false);
let finish = (n - 1, n - 2, false);
visited.insert(start);
let mut queue: VecDeque<State> = VecDeque::new();
queue.push_back(start);

let mut res = 0;
while !queue.is_empty() {
let m = queue.len();
for _ in 0..m {
let state = queue.pop_front().unwrap();
if state == finish {
return res;
}
let i = state.0;
let j = state.1;
let d = state.2;
let right = (i, j + 1, d);
let down = (i + 1, j, d);
let rotate = (i, j, !d);
if d {
if j + 1 < n && grid[i][j + 1] == 0 && grid[i + 1][j + 1] == 0 {
if visited.insert(right) {
queue.push_back(right);
}
if visited.insert(rotate) {
queue.push_back(rotate);
}
}
if i + 2 < n && grid[i + 2][j] == 0 && visited.insert(down) {
queue.push_back(down);
}
} else {
if i + 1 < n && grid[i + 1][j] == 0 && grid[i + 1][j + 1] == 0 {
if visited.insert(down) {
queue.push_back(down);
}
if visited.insert(rotate) {
queue.push_back(rotate);
}
}
if j + 2 < n && grid[i][j + 2] == 0 && visited.insert(right) {
queue.push_back(right);
}
}
}
res += 1;
}
-1
}
}

#[test]
fn test() {
let grid = vec_vec_i32![
[0, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 1, 0, 1, 0],
[0, 1, 1, 0, 0, 0],
[0, 1, 1, 0, 0, 0]
];
let res = 11;
assert_eq!(Solution::minimum_moves(grid), res);
let grid = vec_vec_i32![
[0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1],
[1, 1, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1],
[1, 1, 1, 0, 0, 1],
[1, 1, 1, 0, 0, 0]
];
let res = 9;
assert_eq!(Solution::minimum_moves(grid), res);
}
``````