本文共 1972 字，大约阅读时间需要 6 分钟。

为了找到迷宫中从起点到终点的最短路径并确保路径字典序最小，我们可以使用广度优先搜索（BFS）结合路径优先级处理的方法。

方法思路

解决代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    static final int N = 30, M = 50;
    static char[][] map = new char[N][M];
    static boolean[][] st = new boolean[N][M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < N; i++) {
            map[i] = sc.next().toCharArray();
        }
        bfs();
    }
    private static void bfs() {
        Queue
   
     q = new LinkedList<>();
        q.offer(new Point(0, 0, ""));
        st[0][0] = true;
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };
        char[] directions = { 'U', 'D', 'L', 'R' };
        while (!q.isEmpty()) {
            Point t = q.poll();
            if (t.x == N - 1 && t.y == M - 1) {
                System.out.println(t.s);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int x = t.x + dx[i];
                int y = t.y + dy[i];
                if (x < 0 || x >= N || y < 0 || y >= M) {
                    continue;
                }
                if (map[x][y] == '0' && !st[x][y]) {
                    st[x][y] = true;
                    String path = t.s + directions[i];
                    q.offer(new Point(x, y, path));
                }
            }
        }
    }
    static class Point {
        int x;
        int y;
        String s;
        Point(int x, int y, String s) {
            this.x = x;
            this.y = y;
            this.s = s;
        }
    }
}
   

代码解释

这种方法确保了在找到最短路径的同时，路径的字典序也是最小的。

转载地址：http://czhfk.baihongyu.com/