华为机试题HJ43 迷宫问题

//层次优先遍历的思想，每次找到最近的位置进行外扩，如果外扩到目标节点说明找到了最短路径

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] dx = new int[]{0, 0, 1, -1};
        int[] dy = new int[]{1, -1, 0, 0};
        while (in.hasNext()) {
            int n = in.nextInt(), m = in.nextInt();
            int[][] grid = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    grid[i][j] = in.nextInt();
                }
            }
            String res = "";
            boolean[][] visit = new boolean[n][m];
            //优先级队列存储每个位置上的信息
            PriorityQueue<Cell> minHeap = new PriorityQueue<>();
            minHeap.add(new Cell(0, 0, 0, "(0,0)"));
            while(!minHeap.isEmpty()){
                //每次选最小距离的位置进行扩散访问
                Cell cell = minHeap.poll();
                //如果位置已经被访问过说明有更短的路径到此处，不用继续访问（剪枝）
                if(visit[cell.x][cell.y]){
                    continue;
                }
                visit[cell.x][cell.y] = true;
                //到达目标节点输出结果路径
                if(cell.x == n - 1 && cell.y == m - 1){
                    res = cell.path;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int newX = cell.x + dx[i];
                    int newY = cell.y + dy[i];
                    //四个方向都走下，如果不是墙就记录下位置的到达信息
                    if(!isOverBound(newX, newY, n, m) && grid[newX][newY] == 0){
                        minHeap.add(new Cell(newX, newY, cell.dis + 1, cell.path + "\n(" + newX + "," + newY + ")"));
                    }
                }
            }
            System.out.println(res);
        }
    }

    public static boolean isOverBound(int x, int y, int n, int m){
        return x < 0 || y < 0 || x >= n || y >= m;
    }

    static class Cell implements Comparable<Cell>{
        int x;
        int y;
        //从初始位置到达此处的位置
        int dis;
        //从初始位置到达该位置的路径
        String path;

        public Cell(int x, int y, int dis, String path) {
            this.x = x;
            this.y = y;
            this.dis = dis;
            this.path = path;
        }

        //队列中元素按可达距离排序
        @Override
        public int compareTo(Cell o) {
            return this.dis - o.dis;
        }
    }
}