[图片上传中...(problemJB08.png-3baa06-1575601290342-0)]

problemJB08.png

代码实现

import java.io.*;
import java.util.*;
public class TestE {
    public static void main(String[] args) {
        int n = 30;
        int m=50;
        int[][] g;
        int[] dx = {1,0,0,-1}; // 上下左右四个方向，上：x-1，y不变
        int[] dy = {0,-1,1,0};
        String[] dirs = {"D","L","R","U"};
        try{
            g = readData(n,m);
            // show(g);
            // 获得所有点到终点的距离dist[][]
            int[][] dist = bfs(g,n,m);
            // 从起点开始dfs
            int x = 0;
            int y = 0;
            while (x!=n-1 || y!=m-1){
                for(int i=0;i<4;i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 0) {
                        if (dist[x][y] == dist[nx][ny] + 1) {
                            x = nx;
                            y = ny;
                            System.out.print(dirs[i]);
                        }
                    }
                }
            }
        }catch (Exception e){
            System.out.println(e.getMessage());
        }


    }

    // 将数据读入邻接矩阵
    public static int[][] readData(int n,int m) throws IOException {
        // 获取文件
        File file = new File("/home/chaochao/IdeaProjects/LeetCode/src/十四周/maze.txt");
        //
        BufferedReader fileReader = new BufferedReader(new FileReader(file));
        int edges[][] = new int[n][m];
        // 循环读取所有行
        for (int i = 0; i < n; i++) {
            // 对每一行进行数据写入
            String line = fileReader.readLine();
            for (int j = 0; j < line.length(); j++) {
                String str = String.valueOf(line.charAt(j));
                if (Integer.parseInt(str) == 1) {
                    edges[i][j] = 1;
                }
            }
        }
        fileReader.close();
        return edges;
    }

    public static void show(int[][] edges) {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 迷宫：
     *  题目：要求从左上角走到右下角，路径最短，路径相同的情况下，字典序最小 D<L<R<U
     *
     *  思路：
     *  使用edge【m】【n】表示m点,n距离点30,50的距离
     *  从右下角广度优先搜索，找到距离左上角最短的路径
     */

    public static int[][] bfs(int[][] g,int n,int m){
        int[] dx = {1,0,0,-1}; // 上下左右四个方向，上：x-1，y不变
        int[] dy = {0,-1,1,0};
        LinkedList<int []> queue = new LinkedList<int []>();
        int dist[][] = new int[n][m]; // 保存点到m,n的距离
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dist[i][j] = -1;
            }
        }
        // 自己距离自己的距离为0
        dist[n-1][m-1] = 0;
        int[] initPos = new int[]{n-1,m-1};
        queue.addLast(initPos);
        // 当队列不为空执行
        while (!queue.isEmpty()){
            int[] cur = queue.removeFirst();
            // 遍历四个方向
            for(int i=0;i<4;i++){
                // 当前坐标加上对应方向坐标得出新坐标
                int x = cur[0] + dx[i];
                int y = cur[1] + dy[i];
                // 如果新坐标满足n>x>=0,>my>=0,并且新坐标未被访问过即dist[x][y]==-1,并且当前坐标在图g中可以访问,即g[x][y]==0;
                // 满足上述条件，说明新坐标可以访问，它距离右下角的距离为当前坐标加1，然后入队列
                if(x >= 0 && x<n && y>=0 && y<m && dist[x][y] == -1 && g[x][y] == 0){
                    dist[x][y] = dist[cur[0]][cur[1]] + 1;
                    int[] pos = new int[]{x,y};
                    queue.addLast(pos);
                }
            }
        }
        return dist;
    }
}