用Java做算法提高 学霸的迷宫

题目描述
学霸抢走了大家的作业,班长为了帮同学们找回作业,决定去找学霸决斗。但学霸为了不要别人打扰,住在一个城堡里,城堡外面是一个二维的格子迷宫,要进城堡必须得先通过迷宫。因为班长还有妹子要陪,磨刀不误砍柴功,他为了节约时间,从线人那里搞到了迷宫的地图,准备提前计算最短的路线。可是他现在正向妹子解释这件事情,于是就委托你帮他找一条最短的路线。

数据规模和约定
有20%的数据满足:1<=n,m<=10
有50%的数据满足:1<=n,m<=50
有100%的数据满足:1<=n,m<=500。

输入
第一行两个整数n, m,为迷宫的长宽。
接下来n行,每行m个数,数之间没有间隔,为0或1中的一个。0表示这个格子可以通过,1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方,即左上角,迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里,每次移动算一步。数据保证(1,1),(n,m)可以通过。

输出
第一行一个数为需要的最少步数K。
第二行K个字符,每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径,选择在此表示方法下字典序最小的一个。

样例输入
3 3
001
100
110

样例输出
4
RDRD

我编写的代码

import java.util.ArrayDeque;
import java.util.Scanner;

class point { // 内部类,用于表示当前行走到达点信息
public int x; // 当前到达位置横坐标
public int y; // 当前到达位置纵坐标
public int step; // 行走到当前顶点所用总步数
public String path = ""; // 行走到当前顶点的具体路径

point(int x, int y, int step, String path) {
    this.x = x;
    this.y = y;
    this.step = step;
    this.path = path;
}

}

public class Main {
public static int[][] maze = new int[505][505];
public static int[][] d = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };
public static String ch = "DLRU";// 最小的字典序
public static boolean[][] visited = new boolean[505][505];// 是否被访问过默认值是假
public static point[][] pre = new point[505][505];// 前一个点的信息
public static int n;
public static int m;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    sc.nextLine();// 此处特别注意,输入完整数,下面接着输出字符串,此处处理换行操作
    String[] s = new String[n];
    for (int i = 0; i < n; i++)
        s[i] = sc.nextLine();
    for (int i = 0; i < s.length; i++) {
        char[] c = s[i].toCharArray();
        for (int j = 0; j < m; j++)
            maze[i][j] = c[j] - '0';
    }
    maze[0][0] = maze[n - 1][m - 1] = 0;// 保证入口和出口可以通过
    bfs();
}

public static void bfs() {
    ArrayDeque<point> stack = new ArrayDeque<>();
    stack.offer(new point(0, 0, 0, ""));
    visited[0][0] = true;
    while (stack.size() != 0) {
        point front = stack.poll();// 读队首元素并且出队
        if (front.x == n - 1 && front.y == m - 1) {
            System.out.println(front.step);// 打印最少步数
            print_path(front);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int r = front.x + d[i][0];// 记录移动后的坐标
            int c = front.y + d[i][1];// 记录移动后的坐标
            if (r >= 0 && r < n && c >= 0 && c < m && visited[r][c] == false && maze[r][c] == 0) {
                visited[r][c] = true;
                front.path = ch.toString().substring(i, i + 1);
                pre[r][c] = front;
                stack.push(new point(r, c, front.step + 1, ""));
            }

        }
    }
    return;
}

static void print_path(point p) {
    if (!(p.x == 0 && p.y == 0)) {
        print_path(pre[p.x][p.y]);
    }
    System.out.print(p.path);
}

}

提交到作业网站显示之正确83%,大佬我看看拿错了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问