## 499. The Maze III

There is a **ball** in a maze with empty spaces and walls. The ball can go through empty spaces by rolling **up** (u), **down** (d), **left** (l) or **right** (r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a **hole** in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the **ball position**, the **hole position** and the **maze**, find out how the ball could drop into the hole by moving the **shortest distance**. The distance is defined by the number of **empty spaces** traveled by the ball from the start position (excluded) to the hole (included). Output the moving **directions** by using 'u', 'd', 'l' and 'r'. Since there could be several different shortest ways, you should output the **lexicographically smallest** way. If the ball cannot reach the hole, output "impossible".

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 ball and the hole coordinates are represented by row and column indexes.

**Example 1:**

Input 1:a maze represented by a 2D array 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0Input 2:ball coordinate (rowBall, colBall) = (4, 3)Input 3:hole coordinate (rowHole, colHole) = (0, 1)Output:"lul"Explanation:There are two shortest ways for the ball to drop into the hole. The first way is left -> up -> left, represented by "lul". The second way is up -> left, represented by 'ul'. Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul".

**Example 2:**

Input 1:a maze represented by a 2D array 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0Input 2:ball coordinate (rowBall, colBall) = (4, 3)Input 3:hole coordinate (rowHole, colHole) = (3, 0)Output:"impossible"Explanation:The ball cannot reach the hole.

**Note:**

- There is only one ball and one hole in the maze.
- Both the ball and hole 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 the width and the height of the maze won't exceed 30.

## Rust Solution

```
struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
fn find_shortest_way(maze: Vec<Vec<i32>>, ball: Vec<i32>, hole: Vec<i32>) -> String {
let start_r = ball[0] as usize;
let start_c = ball[1] as usize;
let end_r = hole[0] as usize;
let end_c = hole[1] as usize;
let n = maze.len();
let m = maze[0].len();
let mut states = vec![vec![(std::usize::MAX, "".to_string()); m]; n];
let mut queue: BinaryHeap<(Reverse<usize>, Reverse<String>, usize, usize)> =
BinaryHeap::new();
queue.push((Reverse(0), Reverse("".to_string()), start_r, start_c));
while let Some((Reverse(dist), Reverse(path), r, c)) = queue.pop() {
if r == end_r && c == end_c {
return path;
}
let mut i = r;
let j = c;
let mut d = 0;
let mut p = path.to_string();
p.push('u');
while i > 0 && maze[i - 1][j] == 0 {
i -= 1;
d += 1;
if i == end_r && j == end_c {
break;
}
}
if d > 0 && (d, p.to_string()) < states[i][j] {
states[i][j] = (d, p.to_string());
queue.push((Reverse(dist + d), Reverse(p), i, j));
}
let i = r;
let mut j = c;
let mut d = 0;
let mut p = path.to_string();
p.push('l');
while j > 0 && maze[i][j - 1] == 0 {
j -= 1;
d += 1;
if i == end_r && j == end_c {
break;
}
}
if d > 0 && (d, p.to_string()) < states[i][j] {
states[i][j] = (d, p.to_string());
queue.push((Reverse(dist + d), Reverse(p), i, j));
}
let mut i = r;
let j = c;
let mut d = 0;
let mut p = path.to_string();
p.push('d');
while i + 1 < n && maze[i + 1][j] == 0 {
i += 1;
d += 1;
if i == end_r && j == end_c {
break;
}
}
if d > 0 && (d, p.to_string()) < states[i][j] {
states[i][j] = (d, p.to_string());
queue.push((Reverse(dist + d), Reverse(p), i, j));
}
let i = r;
let mut j = c;
let mut d = 0;
let mut p = path.to_string();
p.push('r');
while j + 1 < m && maze[i][j + 1] == 0 {
j += 1;
d += 1;
if i == end_r && j == end_c {
break;
}
}
if d > 0 && (d, p.to_string()) < states[i][j] {
states[i][j] = (d, p.to_string());
queue.push((Reverse(dist + d), Reverse(p), i, j));
}
}
"impossible".to_string()
}
}
#[test]
fn test() {
let maze = vec_vec_i32![
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 1, 0, 0, 0]
];
let ball = vec![4, 3];
let hole = vec![0, 1];
let res = "lul".to_string();
assert_eq!(Solution::find_shortest_way(maze, ball, hole), res);
let maze = vec_vec_i32![
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 1, 0, 0, 0]
];
let ball = vec![4, 3];
let hole = vec![3, 0];
let res = "impossible".to_string();
assert_eq!(Solution::find_shortest_way(maze, ball, hole), res);
}
```

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