LeetCode 499: The Maze III
Problem Description
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.
Solutions
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";
}Related LeetCode Problems
Loading editor...