## 505. The Maze II

There is a **ball** in a maze with empty spaces and walls. The ball can go through empty spaces by rolling **up**, **down**, **left** or **right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's **start position**, the **destination** and the **maze**, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of **empty spaces** traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

**Example 1:**

Input 1:a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0Input 2:start coordinate (rowStart, colStart) = (0, 4)Input 3:destination coordinate (rowDest, colDest) = (4, 4)Output:12Explanation:One shortest way is : left -> down -> left -> down -> right -> down -> right. The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

**Example 2:**

Input 1:a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0Input 2:start coordinate (rowStart, colStart) = (0, 4)Input 3:destination coordinate (rowDest, colDest) = (3, 2)Output:-1Explanation:There is no way for the ball to stop at the destination.

**Note:**

- There is only one ball and one destination in the maze.
- Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
- The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
- The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.

## Rust Solution

```
struct Solution;
use std::collections::VecDeque;
impl Solution {
fn shortest_distance(maze: Vec<Vec<i32>>, start: Vec<i32>, destination: Vec<i32>) -> i32 {
let n = maze.len();
let m = maze[0].len();
let r = start[0] as usize;
let c = start[1] as usize;
let x = destination[0] as usize;
let y = destination[1] as usize;
let mut dist: Vec<Vec<i32>> = vec![vec![-1; m]; n];
let mut queue: VecDeque<(usize, usize, i32)> = VecDeque::new();
queue.push_back((r, c, 0));
while let Some((i, j, d)) = queue.pop_front() {
if dist[i][j] != -1 && d >= dist[i][j] {
continue;
}
dist[i][j] = d;
let mut step = 0;
let mut di = i;
while di > 0 && maze[di - 1][j] == 0 {
step += 1;
di -= 1;
}
queue.push_back((di, j, d + step));
let mut step = 0;
let mut dj = j;
while dj > 0 && maze[i][dj - 1] == 0 {
step += 1;
dj -= 1;
}
queue.push_back((i, dj, d + step));
let mut step = 0;
let mut di = i;
while di + 1 < n && maze[di + 1][j] == 0 {
step += 1;
di += 1;
}
queue.push_back((di, j, d + step));
let mut step = 0;
let mut dj = j;
while dj + 1 < m && maze[i][dj + 1] == 0 {
step += 1;
dj += 1;
}
queue.push_back((i, dj, d + step));
}
dist[x][y]
}
}
#[test]
fn test() {
let maze: Vec<Vec<i32>> = vec_vec_i32![
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0]
];
let start = vec![0, 4];
let destination = vec![4, 4];
let res = 12;
assert_eq!(Solution::shortest_distance(maze, start, destination), res);
let maze: Vec<Vec<i32>> = vec_vec_i32![
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0]
];
let start = vec![0, 4];
let destination = vec![3, 2];
let res = -1;
assert_eq!(Solution::shortest_distance(maze, start, destination), res);
}
```

Having problems with this solution? Click here to submit an issue on github.