0490. The Maze
https://leetcode.com/problems/the-maze
Description
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 m x n
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:
m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j]
is0
or1
.start.length == 2
destination.length == 2
0 <= startrow, destinationrow <= m
0 <= startcol, destinationcol <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
The maze contains at least 2 empty spaces.
ac
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int row = maze.length, col = maze[0].length;
boolean[][] visited = new boolean[row][col];
return dfs(maze, start[0], start[1], destination, visited);
}
private boolean dfs(int[][] maze, int r, int c, int[] dest, boolean[][] visited) {
// exit, reach destination
visited[r][c] = true;
// 4 directions
for (int i = 0; i < 4; i++) {
int[] loc = rolling(maze, r, c, i);
if (loc[0] == dest[0] && loc[1] == dest[1]) return true; // hit the end
if (visited[loc[0]][loc[1]]) continue; // skip visitd cell
if (dfs(maze, loc[0], loc[1], dest, visited)) return true; // find one valid path
}
return false; // can't find path
}
private int[] rolling(int[][] maze, int r, int c, int direction) {
// 0: up, 1: down, 2:left, 3:right
if (direction == 0) {
while (r - 1 >= 0 && maze[r-1][c] == 0) r--;
} else if (direction == 1) {
while (r + 1 < maze.length && maze[r+1][c] == 0) r++;
} else if (direction == 2) {
while (c - 1 >= 0 && maze[r][c-1] == 0) c--;
} else if (direction == 3) {
while (c + 1 < maze[0].length && maze[r][c+1] == 0) c++;
}
return new int[]{r, c};
}
}
/*
just dfs 4 directions, with helper rolling() func
*/
Last updated
Was this helpful?