题目地址：

https://www.lintcode.com/problem/the-maze-iii/description

给定一个二维$0-1$矩阵，$0$代表空地，$1$代表障碍物。在矩阵里有一个地方是洞，现在有一个小球从某个位置出发进行滑动，每次可以选择一个方向滑动，只有遇到障碍物或者遇到边界，或者遇到洞才会停下来。遇到洞的时候会掉进去，其余情况会停在前面一格的空地上。要求返回这个小球滑动到小洞里的最短路线，路线表示成含u、d、l、r的字符串。如果有多个最短路线，要求返回字典序最小的那个。

思路是Dijkstra算法。开一个新的class来建模坐标点，里面加上路径和距离两个成员变量，这样便于排序。再开一个最小堆，对坐标点先按照距离排序，然后按照路径排序（这样保证出堆的时候的路径是字典序最小的）。接着就直接套用Dijkstra算法模板即可。代码如下：

import java.util.*; public class Solution { class Pair { int x, y, dis; String path; public Pair(int x, int y, int dis, String path) { this.x = x; this.y = y; this.dis = dis; this.path = path; } @Override public boolean equals(Object o) { Pair entry = (Pair) o; return x == entry.x && y == entry.y; } @Override public int hashCode() { return Objects.hash(x, y); } } /** * @param maze: the maze * @param ball: the ball position * @param hole: the hole position * @return: the lexicographically smallest way */ public String findShortestWay(int[][] maze, int[] ball, int[] hole) { // write your code here if (Arrays.equals(ball, hole)) { return ""; } Pair start = new Pair(ball[0], ball[1], 0, ""); PriorityQueue<Pair> minHeap = new PriorityQueue<>((p1, p2) -> p1.dis != p2.dis ? Integer.compare(p1.dis, p2.dis) : p1.path.compareTo(p2.path)); Set<Pair> visited = new HashSet<>(); minHeap.offer(start); while (!minHeap.isEmpty()) { Pair cur = minHeap.poll(); // 走到小洞了，直接返回其路径 if (cur.x == hole[0] && cur.y == hole[1]) { return cur.path; } if (visited.contains(cur)) { continue; } visited.add(cur); for (Pair next : getNexts(cur, maze, hole, visited)) { minHeap.offer(next); } } return "impossible"; } // 返回从cur可以到达的、之前未计算出过最短路的点的列表 private List<Pair> getNexts(Pair cur, int[][] maze, int[] hole, Set<Pair> visited) { List<Pair> nexts = new ArrayList<>(); int x = cur.x, y = cur.y; int[] d = {1, 0, -1, 0, 1}; char[] dir = {'d', 'l', 'u', 'r'}; for (int i = 0; i < 4; i++) { int curx = x, cury = y; int diff = 0; while (inBound(curx, cury, maze) && maze[curx][cury] != 1 && !(curx == hole[0] && cury == hole[1])) { curx += d[i]; cury += d[i + 1]; diff++; } if (!(curx == hole[0] && cury == hole[1])) { curx -= d[i]; cury -= d[i + 1]; diff--; } else { // 走到了小洞，那就返回小洞这个Pair就行了，别的不用管 nexts.clear(); nexts.add(new Pair(curx, cury, cur.dis + diff, cur.path + dir[i])); return nexts; } // 如果这个方向上无法继续移动，就略过这个点 if (diff == 0) { continue; } Pair next = new Pair(curx, cury, cur.dis + diff, cur.path + dir[i]); if (!visited.contains(next)) { nexts.add(next); } } return nexts; } private boolean inBound(int x, int y, int[][] maze) { return 0 <= x && x < maze.length && 0 <= y && y < maze[0].length; } }

时空复杂度$O(mn\log mn)$，空间$O(mn)$。