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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.