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 = [startrow, startcol]` and `destination = [destinationrow, destinationcol]`, return `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: true
Explanation: 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: false
Explanation: 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 <= startrow, destinationrow <= maze.length`
• `0 <= startcol, destinationcol <= 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.

490. The Maze
``````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);
}
``````