## 490. The Maze

There is a ball in a `maze`

with empty spaces (represented as `0`

) and walls (represented as `1`

). The ball can go through the 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 `maze`

, the ball's `start`

position and the `destination`

, where `start = [start`

and _{row}, start_{col}]`destination = [destination`

, return _{row}, destination_{col}]`true`

if the ball can stop at the destination, otherwise return `false`

.

You may assume that **the borders of the maze are all walls** (see examples).

**Example 1:**

Input:maze = [[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]], start = [0,4], destination = [4,4]Output:trueExplanation:One possible way is : left -> down -> left -> down -> right -> down -> right.

**Example 2:**

Input:maze = [[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]], start = [0,4], destination = [3,2]Output:falseExplanation:There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

**Example 3:**

Input:maze = [[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]], start = [4,3], destination = [0,1]Output:false

**Constraints:**

`1 <= maze.length, maze[i].length <= 100`

`maze[i][j]`

is`0`

or`1`

.`start.length == 2`

`destination.length == 2`

`0 <= start`

_{row}, destination_{row}<= maze.length`0 <= start`

_{col}, destination_{col}<= maze[i].length- Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
- The maze contains
**at least 2 empty spaces**.

## Rust Solution

```
struct Solution;
impl Solution {
fn has_path(maze: Vec<Vec<i32>>, start: Vec<i32>, destination: Vec<i32>) -> bool {
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 visited: Vec<Vec<bool>> = vec![vec![false; m]; n];
Self::dfs(r, c, &mut visited, &maze, x, y, n, m);
visited[x][y]
}
fn dfs(
r: usize,
c: usize,
visited: &mut Vec<Vec<bool>>,
maze: &[Vec<i32>],
x: usize,
y: usize,
n: usize,
m: usize,
) {
if visited[r][c] || visited[x][y] {
return;
}
visited[r][c] = true;
let mut i = r;
let mut j = c;
while i > 0 && maze[i - 1][j] == 0 {
i -= 1;
}
if !visited[i][j] {
Self::dfs(i, j, visited, maze, x, y, n, m);
}
i = r;
j = c;
while j > 0 && maze[i][j - 1] == 0 {
j -= 1;
}
if !visited[i][j] {
Self::dfs(i, j, visited, maze, x, y, n, m);
}
i = r;
j = c;
while i + 1 < n && maze[i + 1][j] == 0 {
i += 1;
}
if !visited[i][j] {
Self::dfs(i, j, visited, maze, x, y, n, m);
}
i = r;
j = c;
while j + 1 < m && maze[i][j + 1] == 0 {
j += 1;
}
if !visited[i][j] {
Self::dfs(i, j, visited, maze, x, y, n, m);
}
}
}
#[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 = true;
assert_eq!(Solution::has_path(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 = false;
assert_eq!(Solution::has_path(maze, start, destination), res);
}
```

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