Leetcode 505. The Maze II

Problem Explanation

In this problem, you are given a grid which represents a maze. In the maze, there is a ball that starts at a given position and it needs to get to a destination cell. The ball can move in four directions - up, down, left or right, but it can't stop moving until it hits a wall.

Your task is to find the shortest length of the path from the ball's starting position to the destination cell. If there is no way to reach the destination, you should return -1.

Example

Let's take a simple example. Suppose the given maze is following:

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

The starting position is (0, 4) and the destination is (4, 4).

The shortest way is: left -> down -> left -> down -> right -> down -> right. The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Approach of the Solution

The solution uses the Breadth-First Search (BFS) algorithm to explore the maze. We maintain a queue to store the cells to be visited next, where we always dequeue a cell from the front of the queue, calculate its distance to all its accessible neighbors, and enqueue those neighbors, which haven't been visited yet.

Each cell of the maze is visited at most once and the graph representing the maze has V+E edges, where V is the number of vertices and E is the number of edges. Hence, the time complexity of the solution is O(V+E)=O(n), where n is the total number of cells in the maze.

Python Solution

1
2python
3from queue import Queue
4
5class Solution:
6    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
7        START, DESTINATION = tuple(start), tuple(destination)
8        WALL = 1
9        VERTICAL, HORIZONTAL = [(0, 1), (0, -1)], [(1, 0), (-1, 0)]
10        visited = {START: 0}
11        queue = Queue()
12        queue.put(START)
13        
14        # Helper function to check validity of a cell
15        def isValid(x, y):
16            return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != WALL
17        
18        while queue:
19            cell = queue.get()
20            for direction in VERTICAL+HORIZONTAL:
21                x, y, dist = cell[0], cell[1], visited[cell]
22                
23                # keep moving in current direction until hitting a wall
24                while isValid(x+direction[0], y+direction[1]):
25                    x, y, dist = x+direction[0], y+direction[1], dist+1
26                
27                # if the destination to be visited is shorter via the current cell
28                if (x, y) not in visited or dist < visited[(x, y)]:
29                    visited[(x, y)] = dist
30                    if (x, y) != DESTINATION:
31                        queue.put((x, y))
32         
33        # check if destination is reachable or not
34        if DESTINATION not in visited:
35            return -1
36        return visited[DESTINATION]

Hope this explanation is helpful to you.## JavaScript Solution

In Javascript, to deal with the maze problem, we can utilize the Array and Queue for BFS traversal. Here is the solution in JavaScript,

1
2javascript
3
4function shortestDistance(maze, start, destination) {
5    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
6    const queue = [start];
7    start.push(0);
8    while(queue.length) {
9        let [x, y, step] = queue.shift();
10        if(maze[x][y] <= step && maze[x][y] !== -1) continue;
11        maze[x][y] = step;
12        for(let i=0; i<4; i++) {
13            let dx = x, dy = y, count = 0;
14            while(dx>=0 && dy>=0 && dx<maze.length && dy<maze[0].length && maze[dx][dy] !== 1){
15                dx += directions[i][0];
16                dy += directions[i][1];
17                count++;
18            }
19            dx -= directions[i][0];
20            dy -= directions[i][1];
21            count--;
22            if(maze[dx][dy] === -1 || maze[dx][dy] > count+step){
23                queue.push([dx, dy, count+step]);
24            }
25        }
26    }
27    return maze[destination[0]][destination[1]] === -1? -1 : maze[destination[0]][destination[1]];
28}
29

Java Solution

In Java, we can tailor the solution using Queue for BFS and an array to store the state of each cell in the maze. Here is the approach in Java,

1
2java
3class Solution {
4    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
5    private int m, n;
6
7    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
8        m = maze.length; n = maze[0].length;
9        int[][] distance = new int[m][n]; 
10        for (int[] row: distance) Arrays.fill(row, Integer.MAX_VALUE); 
11        distance[start[0]][start[1]] = 0;
12
13        bfs(maze, start, distance);
14        
15        return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]]; 
16    }
17
18    private void bfs(int[][] maze, int[] start, int[][] distance) {
19        Queue<int[]> queue = new LinkedList<>();
20        queue.add(start);
21        
22        while (!queue.isEmpty()) {
23            int[] cur = queue.poll();
24            for (int[] dir : DIRECTIONS) {
25                int x = cur[0] + dir[0]; 
26                int y = cur[1] + dir[1]; 
27                int count = 0;
28                while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) { 
29                    x += dir[0];
30                    y += dir[1];
31                    count++; 
32                }
33                
34                if (distance[cur[0]][cur[1]] + count < distance[x - dir[0]][y - dir[1]]) {
35                    distance[x - dir[0]][y - dir[1]] = distance[cur[0]][cur[1]] + count;
36                    queue.add(new int[] {x - dir[0], y - dir[1]});
37                }
38            }
39        }
40    }
41}

Each solution implements BFS to find the shortest path to the destination, and the solution in each programming language essentially follows the same logic. Hope these solutions can help you understand how to use BFS to solve this maze problem in Python, JavaScript, and Java.