起因
最近口试遇到好几道题目 大抵题意都是某点登程上、下、左、右行走给出不同的条件判断是否能走到起点，个别咱们都会想到DFS/BFS套用模板解决。
然而求走到起点的某个条件，往往会波及的条件的最值，这时候就须要将BFS中的队列-> Queue 替换成优先级队列 PriorityQueue 主动将属性值排序
(上面题解均基于BFS)
题目1
题意: 给定一个地图 长x宽都是n， 还有一个陷入陷阱所需的等待时间 k。
- 有三种标记0、1、# 别离代表 空地、 墙、 陷阱。每次能够抉择上下左右方向进行走， 走空地没处罚， 走陷阱须要期待 k 秒能够持续走，遇到墙则不能走；
- 从左上点登程，达到右下点，若能达到询问最短时间. 若不能到达右下点则输入"No solution"
- 通过 PriorityQueue 实现小顶堆 对Node实现按工夫升序，这样队列每次弹出的都是time最小的Node
public class GoTrap { static class Node implements Comparable { int x; int y; int time; public Node(int x, int y, int time) { this.x = x; this.y = y; this.time = time; } public Node() { } @Override public int compareTo(Object o) { return this.time - ((Node) o).time; } } static int n; static int k; static char[][] map; static int[][] go = {{0, -1}, {1, 0}, {-1, 0}, {0, 1}}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextint(); k = sc.nextint(); map = new char[n + 1][n + 1]; for (int i = 1; i <= n; i++) { String str = sc.next(); for (int j = 1; j <= n; j++) { map[i][j] = str.charAt(j - 1); } } int val = bfs(); if (val == -1) { System.out.println("No solution"); } else { System.out.println(val); } } private static int bfs() { Boolean[][] vis = new Boolean[n + 1][n + 1]; PriorityQueue<Node> queue = new PriorityQueue<>(); queue.offer(new Node(1, 1, 0)); while (!queue.isEmpty()) { Node node = queue.poll(); if (node.x == n && node.y == n) { return node.time; } for (int i = 0; i < 4; i++) { int tx = node.x + go[i][0]; int ty = node.y + go[i][1]; if (check(new Node(tx, ty, 0)) && !vis[tx][ty]) { if (map[tx][ty] == '0') { queue.offer(new Node(tx, ty, node.time + 1)); vis[tx][ty] = true; } else if (map[tx][ty] == '#') { queue.offer(new Node(tx, ty, node.time + k + 1)); vis[tx][ty] = true; } } } } return -1; } private static Boolean check(Node node) { return node.x > 0 && node.x <= n && node.y > 0 && node.y <= n; }}题目2
- 小昆虫在NM的迷宫中，每次能够朝上、下、左、右走一步，只有走出任一边界就算走出迷宫，“@”代表初始地位，“.”代表空地 可通行，“”代表可毁坏的障碍物
- 从初始地位登程 若能走出输入最小毁坏阻碍数，否则输入-1
- 同理构建小顶堆，Node按毁坏阻碍数count 升序
public class mg { static class Node implements Comparator<Node> { int x; int y; int count; public Node(int x, int y, int count) { this.x = x; this.y = y; this.count = count; } public Node() { } @Override public int compare(Node o1, Node o2) { return o1.count - o2.count; } } static Scanner scanner = new Scanner(System.in); static int n; static int m; static int[][] dir = {{0, -1}, {1, 0}, {-1, 0}, {0, 1}}; static int ex = -1; static int ey = -1; static char[][] map; static int cnt; public static void main(String[] args) { int total = scanner.nextint(); while (total-- > 0) { n = scanner.nextint(); m = scanner.nextint(); map = new char[n][m]; scanner.nextLine(); for (int i = 0; i < n; i++) { map[i] = scanner.nextLine().toCharArray(); for (int j = 0; j < m; j++) { if (map[i][j] == '@') { ex = i; ey = j; } } } int val = bfs(ex, ey); System.out.println(val); } } static int bfs(int x, int y) { Boolean[][] visit = new Boolean[n][m]; Queue<Node> queue = new PriorityQueue<>(new Node()); queue.add(new Node(x, y, 0)); Node next = new Node(); while (!queue.isEmpty()) { Node node = queue.poll(); visit[node.x][node.y] = true; if (node.x + 1 > n - 1 || node.x - 1 < 0 || node.y + 1 > m - 1 || node.y - 1 < 0) { return node.count; } for (int i = 0; i < 4; i++) { next.x = node.x + dir[i][0]; next.y = node.y + dir[i][1]; if (!visit[next.x][next.y]) { if (map[next.x][next.y]=='*') { queue.add(new Node(next.x,next.y,next.count+1)); } else if (map[next.x][next.y]=='.') { queue.add(new Node(next.x,next.y,next.count)); } } } } return -1; }}