关于java:两道秋招笔试题解JavaBFS优先级队列

起因

最近口试遇到好几道题目 大抵题意都是某点登程上、下、左、右行走给出不同的条件判断是否能走到起点，个别咱们都会想到 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

• 小昆虫在 N M 的迷宫中，每次能够朝上、下、左、右走一步，只有走出任一边界就算走出迷宫，“@”代表初始地位，“.”代表空地 可通行，“”代表可毁坏的障碍物
• 从初始地位登程 若能走出输入最小毁坏阻碍数，否则输入 -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;
    }
}