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