Leetcode 490. The Maze

Problem Explanation:

In this problem, we are given a 2D array (or grid) representing a maze, a starting position, and a destination. The numbers in the maze are either 0 (which represents open space) or 1 (which represents a wall). Our goal is to determine if it's possible to get to the destination from the starting point by moving only in four directions (up, down, left, and right) and only stopping when hitting a wall.

The ball starts at the start coordinate (row, col). Every time the ball moves, it goes in the selected direction until it hits a wall. The ball then has the choice to select a new direction to start moving in, and the same rule (moving in the selected direction until it hits a wall) applies.

Let's examine Example 1:

The maze is as follows:

1
2
30 0 1 0 0
40 0 0 0 0
50 0 0 1 0
61 1 0 1 1
70 0 0 0 0

We start at position (0,4). We then move as follows: left -> down -> left ->down -> right -> down -> right, and arrive at position (4,4), which is the destination point. So the output is true.

If the destination is blocked or unreachable, such as in example 2, the output is false.

Solution Approach:

The approach used in this problem is Breadth-First Search (BFS). BFS is a graph traversal algorithm which traverses the graph level by level. This property of BFS is useful in this problem because we need to traverse the maze by going in one direction until we hit a wall, update our position, and then continue on with the next direction in the queue.

A queue data structure is used to store each position as we navigate our way in the maze. Also, an auxiliary 2D array (same size as the input maze), named seen, is used to keep track of the cells that the ball has already visited.

The BFS begins from the start point. For each point, we simulate the ball's movement in four direction (up, down, right, and left). For each direction, the ball keeps on rolling until it hits a wall. If the ball hits the destination during this process, then return true. Else, if it hits a wall and it is not already visited, then add the wall point to the queue to continue the BFS.

This process continues until we have exhausted all possible directions. If the ball never reaches the destination coordinate, return false.

C++ Code:

1
2c++
3class Solution {
4public:
5    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
6        // Possible directions to move
7        const vector<int> dirs{0, 1, 0, -1, 0};
8        
9        // Maze dimensions
10        const int m = maze.size();
11        const int n = maze[0].size();
12        
13        // Initialize a queue and mark start position as visited
14        queue<pair<int, int>> q{{{start[0], start[1]}}};
15        vector<vector<bool>> seen(m, vector<bool>(n));
16        seen[start[0]][start[1]] = true;
17
18        // BFS
19        while (!q.empty()) {
20            // Get current position
21            const auto [i, j] = q.front(); q.pop();
22            
23            // Check all 4 directions
24            for (int k = 0; k < 4; ++k) {
25                int x = i;
26                int y = j;
27                
28                // Keep moving in one direction until a wall is hit
29                while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
30                    x += dirs[k];
31                    y += dirs[k + 1];
32                }
33                
34                // If destination is reached, return true
35                if (x == destination[0] && y == destination[1])
36                    return true;
37                
38                // If this is a new position, add it to the queue
39                if (!seen[x][y]) {
40                    q.emplace(x, y);
41                    seen[x][y] = true;
42                }
43            }
44        }
45
46        // Destination not reached
47        return false;
48    }
49
50private:
51    // Check if the position is valid (within boundaries and not a wall)
52    bool isValid(const vector<vector<int>>& maze, int x, int y) {
53        return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size() && maze[x][y] == 0;
54    }
55};

Java Code:

1
2java
3class Solution {
4  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
5    int m = maze.length;
6    int n = maze[0].length;
7    boolean[][] visited = new boolean[m][n];
8
9    // BFS queue
10    Queue<int[]> q = new LinkedList<>();
11    q.offer(start);
12
13    // Directions: left, down, right, up
14    int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
15
16    while (!q.isEmpty()) {
17      int[] cur = q.poll();
18
19      if (cur[0] == destination[0] && cur[1] == destination[1]) return true;
20
21      for (int[] dir : dirs) {
22        int x = cur[0] + dir[0];
23        int y = cur[1] + dir[1];
24        
25        // Roll the ball
26        while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
27          x += dir[0];
28          y += dir[1];
29        }
30
31        // Step back once to hit the wall
32        x -= dir[0];
33        y -= dir[1];
34
35        // Check the stop point
36        if (!visited[x][y]) {
37          visited[x][y] = true;
38          q.offer(new int[] {x, y});
39        }
40      }
41    }
42
43    return false;
44  }
45}

Python Code:

1
2python
3class Solution:
4    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
5        m, n, queue, seen = len(maze), len(maze[0]), collections.deque([(start[0], start[1])]), set((start[0], start[1]))
6        dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
7        
8        while queue:
9            x, y = queue.popleft()
10            if [x, y] == destination:
11                return True
12            
13            # Move in all possible directions
14            for dx, dy in dirs:
15                nx, ny = x, y
16                while 0 <= nx+dx < m and 0 <= ny+dy < n and not maze[nx+dx][ny+dy]:
17                    nx += dx
18                    ny += dy
19                
20                # Only check this new starting point (nx, ny) if we never visited it before
21                if (nx, ny) not in seen:
22                    seen.add((nx, ny))
23                    queue.append((nx, ny))
24        
25        # If no path found
26        return False

JavaScript Code:

1
2javascript
3var hasPath = function(maze, start, destination) {
4    let directions = [[-1,0],[0,-1],[1,0],[0,1]], // up, left, down, right
5        queue = [start], 
6        visited = Array.from({length: maze.length}, () => Array(maze[0].length));
7    
8    visited[start[0]][start[1]] = true;
9    
10    while (queue.length > 0) {
11        let [x, y] = queue.shift();
12        
13        if (x === destination[0] && y === destination[1]){
14            return true;
15        }
16        
17        // Try to go in all 4 directions from current point
18        for (let dir of directions) {
19            let newX = x, newY = y;
20            
21            // Keep moving in the direction (dir) until wall hit
22            while (newX + dir[0] >= 0 && newX + dir[0] < maze.length && newY + dir[1] >= 0 && newY + dir[1] < maze[0].length && !maze[newX + dir[0]][newY + dir[1]]){
23                newX += dir[0];
24                newY += dir[1];
25            }
26            
27            // Check the stop position and add to queue if it is visited first time
28            if (!visited[newX][newY]){
29                queue.push([newX, newY]);
30                visited[newX][newY] = true;
31            }
32        }
33    }
34    
35    return false;
36};

In all of these solutions, we are essentially following the same process: run a breadth-first search on our maze, marking cells as visited once we've processed them, and return true as soon as the destination is reached, or false if it never is. In the worst case, our runtime is proportional to the size of our maze, i.e., O(mn) where m and n are the number of rows and columns in our maze respectively.This is because we need to visit every cell in our maze at least once during our traversal. The space complexity is similarly O(mn) as we need to maintain a visited grid and a queue for keeping track of our movement in the maze. This worst case would occur when destination is unsolvable and we would have to traverse the whole maze.

One potential optimization for this solution could involve tweaking our BFS algorithm to instead perform a depth-first search (DFS). DFS could potentially reach the destination faster in certain types of mazes. But remember that DFS does not guarantee the shortest path if that is needed.

In certain problem variants, we might be asked not only whether a path exists, but to also find the shortest possible path to the destination. In such scenario, the above BFS solution would not work directly since BFS in this case would not always result in the shortest path due to the bouncing nature of the ball. We would need to add more conditions in our algorithm to keep track of the path taken.

Similarly in some cases, we could take advantage of heuristics such as the Euclidean distance (the square root of the sum of the squares of the differences of the coordinates) or the Manhattan distance (the sum of the absolute values of the differences of the coordinates). In those cases, an A* search algorithm could be used, which is a combination of Best-first Search(BFS which is good at exploring nearby positions) and Dijkstra's Algorithm(which is good at exploring the destination). This algorithm works by assigning a priority to each cell, and always visiting the cell with the highest priority first, which could speed up our search significantly.

Overall, our solution provides a solid foundation for performing BFS on a grid, which can be easily extended and modified to handle more complex maze problems. Depending on the specific requirements of your problem, different traversal or pathfinding algorithms can be more suitable, so as always it is important to understand the specific requirements and constraints of your problem before choosing an approach.