The Maze

Medium

There is aballin a maze with empty spaces and walls. The ball can go through empty spaces by rollingup,down,leftorright, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball'sstart position, thedestinationand themaze, determine whether the ball could stop at the destination.

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 start and destination coordinates are represented by row and column indexes.

Example 1:

Input 1: a maze represented by a 2D array

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

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: true

Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2:

Input 1: a maze represented by a 2D array

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

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)

Output: false

Explanation: There is no way for the ball to stop at the destination.

Note:

1. There is only one ball and one destination in the maze.
2. Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3. 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.
4. The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.

Analysis

DFS 深度优先搜索 In order to do this traversal, one of the simplest schemes is to undergo depth first search. In this case, we choose one path at a time and try to go as deep as possible into the levels of the tree before going for the next path.

In order to implement this, we make use of a recursive function dfs(maze, start, desination, visited).

BFS 广度优先搜索

we try to explore the search space on a level by level basis. We try to move in all the directions at every step. When all the directions have been explored and we still don't reach the destination, then only we proceed to the new set of traversals from the new positions obtained.

Use queue to implement BFS.

visited[][] for visited positions.

initialize:

queue.offer(start);
visited[start][start] = true;

To get the next "Stopped Position"

int nrow = pos;
int ncol = pos;
while (canRoll(maze, nrow + dir, ncol + dir)) {
nrow += dir;
ncol += dir;
}

Trick:

Solution

DFS - ( modularized) - (6ms, 93.42%)

class Solution {

// UP: {-1, 0}, RIGHT: {0, 1}, DOWN: {1, 0}, LEFT: {0, -1}
private static int DIR[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze.length;
boolean[][] visited = new boolean[m][n];

return traverse(maze, start, destination, visited);
}

private boolean traverse(int[][] maze, int[] position, int[] destination, boolean[][] visited) {
if (visited[position][position]) {
return false;
}
if (Arrays.equals(position, destination)) {
return true;
}

visited[position][position] = true;

// Roll the ball for `UP, RIGHT, DOWN, LEFT` four directions
for (int i = 0; i < DIR.length; i++) {
int[] newPosition = roll(maze, position, DIR[i]);

if (traverse(maze, newPosition, destination, visited)) {
return true;
}
}

return false;
}

// Roll the ball based on current position and direction, return new stopped postion
private int[] roll(int[][] maze, int[] position, int[] direction) {
int row = position;
int col = position;

while (canRoll(maze, row + direction, col + direction)) {
row += direction;
col += direction;
}
return new int[] {row, col};
}

// Using next row, col position to check if a ball can roll
private boolean canRoll(int[][] maze, int nrow, int ncol) {
int m = maze.length;
int n = maze.length;

if (nrow < 0 || nrow >= m || ncol < 0 || ncol >= n) {
return false;
}
if (maze[nrow][ncol] == 1) {
return false;
}
return true;
}
}
• Time complexity :O(mn). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and coloumns of the maze.

• Space complexity :O(mn). visited array of size m*n is used.

BFS - (6ms, 84.21%)

class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze.length;
Deque<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[m][n];
int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

queue.offer(start);
visited[start][start] = true;

while (!queue.isEmpty()) {
int[] pos = queue.poll();
if (pos == destination && pos == destination) {
return true;
}

for (int[] dir: dirs) {
int nrow = pos;
int ncol = pos;
while (canRoll(maze, nrow + dir, ncol + dir)) {
nrow += dir;
ncol += dir;
}

if (!visited[nrow][ncol]) {
queue.offer(new int[] {nrow, ncol});
visited[nrow][ncol] = true;
}
}
}
return false;
}

private boolean canRoll(int[][] maze, int nrow, int ncol) {
int m = maze.length;
int n = maze.length;
return nrow < m && nrow >= 0 && ncol < n && ncol >= 0 && maze[nrow][ncol] == 0;
}
}

Reference

https://leetcode.com/problems/the-maze/solution/