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]
is0
or1
.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.
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.