490. The Maze

leetcode_490.md

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).

Link to the original problem

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.

Constraints:

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] is 0 or 1.
• 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.

Idea

1. First I want to say that this is not exactly a shortest path problem. However, both logic are so similar that I believe they fall into the same category.
2. Let's see why.
3. If you remember what we have done so far for the shortest path questions, you'll realize the most important part is how we do BFS.
4. To generalize the logic a little bit, you'll find, we don't necessarily need the grid/matrix/maze to do BFS (like what we did in this hidden grid), as long as we can find the next-level cells to proceed, right?
5. So for this question, we have the grid, so we don't have to build one. The difference is that when we traverse the maze, we won't be able to stop unless we hit a wall.
6. So in a traditional grid, when we do BFS we can get the next-level cells by moving up/down/left/right. In this question, as long as we can find the next-level cells by "rolling until we hit a wall", then it's the same question.
7. That's easy, we can just have a helper function that walks from [x,y] following the direction's delta [dx,dy], then we'll find the next-level cells.
8. The code is astoundingly simiar to the previous questions, so it should explain itself well.

Solution

Javascript

const hasPath = function(maze, start, dest) {
  const R = maze.length, C = maze[0].length;
  const inRange = (i, j) => (i >= 0 && i < R && j >= 0 && j < C && !maze[i][j]);
  const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  const queue = [start], visited = new Set();

  while (queue.length) {
    const [x, y] = queue.shift();
    if (x == dest[0] && y == dest[1]) return true;
    
    for (const [dx, dy] of DIRS) {
      if (inRange(x + dx, y + dy)) {
        const nextPosition = walk(x, y, dx, dy);
        const key = nextPosition.join();
        if (!visited.has(key)) {
          visited.add(key);
          queue.push(nextPosition);
        }
      }
    }
  }
  return false;

  function walk(x, y, dx, dy) {
    while (inRange(x+dx, y+dy)) x += dx, y += dy;
    return [x, y];
  }
};

References

1. Leetcode 1730
2. Leetcode 1091
3. Leetcode 1293
4. Leetcode 864
5. Leetcode 317
6. Leetcode 1778