LeetCode 499: The Maze III Solution

Master LeetCode problem 499 (The Maze III), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

499. The Maze III

Hard

Array String Depth-First Search Breadth-First Search Graph Heap (Priority Queue)Matrix Shortest Path

Problem Explanation

Explanation

The problem "The Maze III" involves finding the shortest path in a maze from a starting position to a destination position. The maze is represented as a 2D array where 0 indicates empty space and 1 indicates an obstacle. The ball can move in four directions: up, down, left, or right until it hits a wall.

To solve this problem, we can use Dijkstra's algorithm with a priority queue to explore all possible paths from the starting position to the destination. We need to keep track of the distance traveled, the path taken, and the position of the ball at each step. When the ball reaches the destination, we update the shortest path found so far.

Solution Code

import java.util.*;

class Point {
    int x, y, dist;
    String path;

    public Point(int x, int y, int dist, String path) {
        this.x = x;
        this.y = y;
        this.dist = dist;
        this.path = path;
    }
}

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
    int m = maze.length, n = maze[0].length;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    String[] dirStrs = {"u", "d", "l", "r"};

    PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
    pq.offer(new Point(ball[0], ball[1], 0, ""));

    int[][] dist = new int[m][n];
    for (int i = 0; i < m; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE);
    }
    dist[ball[0]][ball[1]] = 0;

    while (!pq.isEmpty()) {
        Point curr = pq.poll();
        if (curr.x == hole[0] && curr.y == hole[1]) {
            return curr.path;
        }

        for (int i = 0; i < 4; i++) {
            int x = curr.x, y = curr.y, d = curr.dist;
            String path = curr.path;
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && (x != hole[0] || y != hole[1])) {
                x += dirs[i][0];
                y += dirs[i][1];
                d++;
            }

            if (dist[curr.x][curr.y] + d < dist[x - dirs[i][0]][y - dirs[i][1]]) {
                dist[x - dirs[i][0]][y - dirs[i][1]] = dist[curr.x][curr.y] + d;
                pq.offer(new Point(x - dirs[i][0], y - dirs[i][1], dist[x - dirs[i][0]][y - dirs[i][1]], path + dirStrs[i]));
            }
        }
    }

    return "impossible";
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 499 (The Maze III)?

This page provides optimized solutions for LeetCode problem 499 (The Maze III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 499 (The Maze III)?

The time complexity for LeetCode 499 (The Maze III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 499 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 499 in Java, C++, or Python.

Back to LeetCode Solutions