迷宫 III

/*
 * 思路：
 * 1. 使用广度优先搜索（BFS）在迷宫中寻找从起点到终点的最短路径。
 * 2. 利用Java Streams来处理优先队列中的元素。
 * 3. 路径信息通过字符串的形式累积，优先选择字典序小的路径。
 */
import java.util.*;
import java.util.stream.Stream;
 
public class SolutionStream {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final char[] DIR_CHARS = {'u', 'd', 'l', 'r'};
 
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length, n = maze[0].length;
        PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.dist == b.dist ? a.path.compareTo(b.path) : a.dist - b.dist);
        pq.offer(new Point(ball[0], ball[1], 0, ""));
        boolean[][] visited = new boolean[m][n];
        visited[ball[0]][ball[1]] = true;
 
        while (!pq.isEmpty()) {
            Point p = pq.poll();
            if (p.x == hole[0] && p.y == hole[1]) return p.path;
 
            for (int i = 0; i < DIRECTIONS.length; i++) {
                int[] dir = DIRECTIONS[i];
                int x = p.x, y = p.y, dist = p.dist;
                while (x + dir[0] >= 0 && x + dir[0] < m && y + dir[1] >= 0 && y + dir[1] < n && maze[x + dir[0]][y + dir[1]] == 0) {
                    x += dir[0];
                    y += dir[1];
                    dist++;
                    if (x == hole[0] && y == hole[1]) break;
                }
                if (visited[x][y]) continue;
                visited[x][y] = true;
                pq.offer(new Point(x, y, dist, p.path + DIR_CHARS[i]));
            }
        }
        return "impossible";
    }
 
    private static class Point {
        int x, y, dist;
        String path;
 
        Point(int x, int y, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
    }
}