Leetcode 499. The Maze III

Problem Explanation:

In this problem, we have a maze which is represented by a 2D binary array. The walls of the maze are represented by 1, and the empty spaces are represented by 0. Within this maze, there is a ball and a hole. The ball is able to roll in the four cardinal directions, but once it starts rolling, it does not stop until it hits a wall.

The goal of the task is to find the shortest path for the ball to fall into the hole. The path length is measured as the number of empty spaces the ball passes through, and we want to return the shortest path in terms of a string of directions ("u" for up, "d" for down, "l" for left, "r" for right). If there are multiple shortest paths, we want the lexicographically smallest path.

If it is impossible for the ball to reach the hole, we must return the string "impossible".

Approach of the Solution:

The solution provided here takes a depth-first search (DFS) approach to the problem. Starting from the ball’s starting position, it explores all possible paths where the ball can roll until it hits a wall. If there are multiple paths with the same shortest distance, it chooses the lexicographically smaller one.

As the DFS explores potential paths, the solution maintains the current path string and the number of steps that have been taken. If a hole is encountered and the number of steps taken is less than the previously found minimum number of steps, the current path is updated.

If there is a position on the maze that has been visited before, the DFS won't go that way unless the number of steps it would take to reach the hole from there is less than the last time it was visited.

Example:

In the following example, where "B" denotes the ball's position, "H" denotes the hole's position, "#" denotes a wall, " " denotes an empty space.

Let's take the maze as:

1
2
3  H  
4#####
5B    

The Ball (B) will reach the Hole (H) following the path as "uuuu" (up 4 times).

This is because, from its current position, the ball can only roll up (or down, hitting a wall). If it rolls up, it will stop before hitting a wall or the hole. Then, it can take another step up to reach the hole. This is the shortest path, and also the only path.

Python Solution:

1
2python
3class Solution:
4    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
5        ball, hole = tuple(ball), tuple(hole)
6        m, n = len(maze), len(maze[0])
7        heap = [(0, "", ball)]
8        dirs = {"u": (-1, 0), "r": (0, 1), "l": (0, -1), "d": (1, 0)}
9        visited = {ball: (0, "")}
10        
11        while heap:
12            dist, path, pos = heapq.heappop(heap)
13            if pos == hole: return path
14            for d in "urld":
15                dx, dy = dirs[d]
16                x, y, dist2 = pos[0] + dx, pos[1] + dy, 0
17                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0 and (x, y) != hole:
18                    x, y, dist2 = x + dx, y + dy, dist2 + 1
19                stop = (x - dx, y - dy)
20                if stop not in visited or dist + dist2 < visited[stop][0] or (dist + dist2 == visited[stop][0] and path + d < visited[stop][1]):
21                    visited[stop] = (dist + dist2, path + d)
22                    heapq.heappush(heap, (dist + dist2, path + d, stop))
23        return "impossible"

The python solution involves using a heap data structure and pushing the initial state (0 distance, empty path, and the starting ball position) into the heap. Later, iteratively, nodes are popped from the heap, and for each direction, a new prospective state is calculated, pushed into the heap, and the visited dict is updated. If a hole is encountered, the path is returned.Javascript Solution:

1
2javascript
3class Node {
4    constructor(x, y, l, s) {
5        this.x = x;
6        this.y = y;
7        this.l = l;
8        this.s = s;
9    }
10}
11
12let shortestDistance = function(maze, start, destination) {
13    let dirs = [["u", -1, 0], ["r", 0, 1], ["l", 0, -1], ["d", 1, 0]];
14    let pq = [new Node(start[0], start[1], 0, "")];
15    let m = maze.length;
16    let n = maze[0].length;
17    let visited = Array(m).fill(false).map(() => Array(n).fill(false));
18    while (pq.length > 0) {
19        let cur = pq.pop();
20        let x = cur.x;
21        let y = cur.y;
22        if (x === destination[0] && y === destination[1]) {
23            return cur.s;
24        }
25        if (visited[x][y]) {
26            continue;
27        }
28        visited[x][y] = true;
29        for (let dir of dirs) {
30            let nx = x;
31            let ny = y;
32            let l = cur.l;
33            while (isValid(maze, nx + dir[1], ny + dir[2])) {
34                nx += dir[1];
35                ny += dir[2];
36                l += 1;
37            }
38            let path = cur.s + dir[0];
39            pq.push(new Node(nx, ny, l, path));
40            pq.sort((a, b) => a.l - b.l || a.s.localeCompare(b.s));
41        }
42    }
43    return "impossible";
44}
45
46let isValid = function(maze, x, y) {
47    let m = maze.length;
48    let n = maze[0].length;
49    return x >= 0 && y >= 0 && x < m && y < n && maze[x][y] === 0;
50}

The javascript version of the solution follows the same approach as the python one. The only difference is the implementation details specific to the syntax and features of Javascript.

Java Solution:

1
2java
3public class Solution {
4    class Node {
5        int x,y,l;
6        String s;
7        public Node(int _x, int _y,int _l,String _s){
8            x=_x;
9            y=_y;
10            l=_l;
11            s=_s;
12        }
13    }
14    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
15        int[][]dist=new int[maze.length][maze[0].length];
16        for(int[] row:dist) Arrays.fill(row, Integer.MAX_VALUE);
17        PriorityQueue<Node> list=new PriorityQueue<>((o1, o2) -> o1.l==o2.l ? o1.s.compareTo(o2.s) : o1.l-o2.l);
18        list.offer(new Node(ball[0],ball[1],0,""));
19        int[][] dir={{-1,0},{0,1},{1,0},{0,-1}};
20        String[] ds={"u","r","d","l"};
21        while (!list.isEmpty()){
22            Node cur=list.poll();
23            if(cur.l>=dist[cur.x][cur.y]) continue;
24            dist[cur.x][cur.y]=cur.l;
25            for(int i=0;i<4;i++){
26                int x=cur.x,y=cur.y,l=cur.l;
27                while (x>=0 && y>=0 && x<maze.length && y<maze[0].length && maze[x][y]==0 
28                       && (x!=hole[0] || y!=hole[1])){
29                    x += dir[i][0];
30                    y += dir[i][1];
31                    l++;
32                }
33                if(x!=hole[0] || y!=hole[1]){
34                    x -= dir[i][0];
35                    y -= dir[i][1];
36                    l--;
37                }
38                list.offer(new Node(x, y, l, cur.s + ds[i]));
39            }
40        }
41        return dist[hole[0]][hole[1]]==Integer.MAX_VALUE ? "impossible" : list.poll().s;
42    }
43}

Just like the aforementioned solutions, the Java solution also uses a priority queue. In this solution, four directions are defined to guide the movement of the ball. From the current position, moves in each direction are validated until the ball hits a wall or the hole. Valid moves are enqueued, and this process continues until the queue is empty. If the destination has been reached, the path is returned, otherwise "impossible" is returned.

In each solution, the priority queue is sorted first according to path length, and then lexicographically by the path string. This ensures that if several paths of equal length are found, the lexicographically smallest one will be returned.