目录
问题描述
学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
第一行两个整数n， m，为迷宫的长宽。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
数据规模和约定
有20%的数据满足：1<=n,m<=10
有50%的数据满足：1<=n,m<=50
有100%的数据满足：1<=n,m<=500。
方向一：（dfs：未AC）
解题思路：
深度搜索，从起点出发，朝该点的四个方向探测，只要坐标点合法，便加入路径中，当遇到“死胡同”或已经走到终点时，及时回溯，由于即时按字典序探测也可能不会找到最少步数，所以需要将所有可能路径都探测到，从中选取步数和字典序最小的一个。由于数据规模太大，会大量递归用到栈，所以时间上会超时，空间上会爆栈超内存，只能作为一种思路，不可取。
java代码：
import java.awt.Point;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int [][]map = new int[n][m];
for(int i = 0; i < n;i++) {
String str = br.readLine();
for(int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j) - '0';
}
}
Temp147 obj = new Temp147(n, m, map);
obj.dfs();
}
}
class Temp147{
int [][]map;
boolean [][]vis;
int n;
int m;
int step = 0;
Point start = new Point(1, 1);
int []dx = {1, 0, 0, -1};//下 左 右 上
int []dy = {0, -1, 1, 0};
char []c = new char[] {'D', 'R', 'L', 'U'};
StringBuilder builder = new StringBuilder();//拼接路径
List<String> list = new ArrayList<>();
public Temp147(int n, int m, int [][]mp) {
this.n = n;
this.m = m;
map = new int[n + 2][m + 2];
vis = new boolean[n + 2][m + 2];
for(int i = 0; i < m + 2; i++) {//初始化地图
map[0][i] = 1;
map[n + 1][i] = 1;
}
for(int i = 0; i < n + 2; i++) {
map[i][0] = 1;
map[i][m + 1] = 1;
}
for(int i = 1; i < 1 + n; i++) {
for(int j = 1; j < 1 + m; j++) {
map[i][j] = mp[i - 1][j - 1];
}
}
}
public void dfs() {
dfs(start);
list.sort(new Comparator<String>() {//将所有可能的路径按步数和字典序排序
@Override
public int compare(String o1, String o2) {
int len1 = o1.length();
int len2 = o2.length();
if(len1 != len2) {
return len1 - len2;
}else {
return o1.compareTo(o2);
}
}
});
System.out.println(list.get(0).length());
System.out.println(list.get(0));
}
public void dfs(Point p) {
if(p.x == n && p.y == m) {//遍历到终点时
list.add(builder.toString());//添加路径
return;
}
for(int i = 0; i < 4; i++) {
int x = p.x + dx[i];
int y = p.y + dy[i];
if(map[x][y] == 0 && !vis[x][y]) {//坐标合法且为被访问
vis[x][y] = true;
step++;//步数加一
builder.append(c[i]);
dfs(new Point(x, y));
vis[x][y] = false;//回溯
step--;
builder.deleteCharAt(builder.length() - 1);
}
}
}
}提交截图：
方向二：（bfs：AC）
解题思路：
要求解从入口到出口的最少步数，还需要按字典序输出。可以将地图上每点的横纵坐标坐标封装进类，从入口开始，将每点按字典序入队和出队（广度搜索），当首先遍历到终点时，表明已经找到了最少步数。
要判断遍历到的每个点是否合法，可以提前将地图的一圈标记为不可走（为1时不可达），即当某点不为1并且没有访问过该点时，表明该点合法。
对路径的处理：
对路径的处理有两种方法：
①在程序中维护一个二维数组，表示路径，将每可以走一步的范围都标志为前一步加一，最容易想到的是入口为0，朝后依次递增（正向遍历）。但在找路径时，当陷入“死胡同”时，不能回溯使输出路径错误。因此，需要倒着从终点往起点遍历，可以找出路径（利用下一步加一等于上一步），此时还需要将存储字典序的数组值“上下左右”都写反，此时拼接出的便是倒序的路径。（也可以与上述思路相反的，即将终点与起点调换的逆向遍历）。
②：直接将路径和步数随坐标一起封装进类，即该类的每个对象都能表示出实时的地图上的某点的横纵坐标，到起点的步数，从起点到该点的路径。遍历到出口时，直接输出终点的信息即可。
对路径两种处理方式的比较：
方式一由于只有一个二维数组，免去了对坐标对象新增属性的开销，较省内存，但思路太绕（其实就是先记录先序路径，再遍历输出路径），不好理解，还容易出错。方式二稍耗内存，但容易理解，还不易出错。推荐方式二做法。
java代码：（二维数组求路径）（正向遍历）
import java.io.*;
import java.util.*;
public class Main0147bbb {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int [][]map = new int[n][m];
for(int i = 0; i < n;i++) {
String str = br.readLine();
for(int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j) - '0';
}
}
Temp147bbb obj = new Temp147bbb(n, m, map);
obj.bfs();
}
}
class Temp147bbb{
int [][]map;//处理后的地图（包含每个点是否可以走）
int [][]path;//标志地图中可走的每点是否已经访问
int n;//地图实际行数
int m;//地图实际列数
int []dx = {1, 0, 0, -1};//下 左 右 上
int []dy = {0, -1, 1, 0};
char []c = new char[] {'U', 'R', 'L', 'D'};//按字典序搜索
public Temp147bbb(int n, int m, int [][]mp) {
this.n = n;
this.m = m;
map = new int[n + 2][m + 2];
path = new int[n + 2][m + 2];
for(int i = 0; i < m + 2; i++) {//处理地图的上下边界
map[0][i] = 1;
map[n + 1][i] = 1;
}
for(int i = 0; i < n + 2; i++) {//处理地图的左右边界
map[i][0] = 1;
map[i][m + 1] = 1;
}
for(int i = 1; i < 1 + n; i++) {//初始化地图
for(int j = 1; j < 1 + m; j++) {
map[i][j] = mp[i - 1][j - 1];
}
}
for(int i = 0; i < n + 2; i++) {
for(int j = 0; j < m + 2; j++) {
path[i][j] = -1;
}
}
path[1][1] = 0;//将入口作为“第0步”
}
public void bfs() {
Queue<Point147bbb> qu = new LinkedList<>();
qu.add(new Point147bbb(1, 1));//起点入队
while(!qu.isEmpty()) {
Point147bbb point = qu.poll();
if(point.x == n && point.y == m) {//遍历到终点时，由于是按字典序排序的，可以直接退出
break;
}
for(int i = 0; i < 4; i++) {
int x = point.x + dx[i];//找点的上下左右
int y = point.y + dy[i];
if(map[x][y] == 0 && path[x][y] == -1) {//目标点合法且未被遍历
qu.add(new Point147bbb(x, y));
path[x][y] = path[point.x][point.y] + 1;//下一步为上个点步数加一
}
}
}
System.out.println(path[n][m]);//该点为总步数
StringBuilder ans = new StringBuilder();
Point147bbb point = new Point147bbb(n, m);//从起点开始
for(int i = 0; i < 4; i++) {//遍历步数，得到路径
int x = point.x + dx[i];
int y = point.y + dy[i];
if(path[x][y] != -1 && path[x][y] == path[point.x][point.y] - 1) {//还需保证合法点
ans.append(c[i]);
point = new Point147bbb(x, y);
i = -1;//使进行下一趟
}
}
System.out.println(ans.reverse());
}
}
class Point147bbb{//坐标信息
int x;
int y;
public Point147bbb(int x, int y) {
this.x = x;
this.y = y;
}
}java代码：（二维数组求路径）（逆向遍历）
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int [][]map = new int[n][m];
for(int i = 0; i < n;i++) {
String str = br.readLine();
for(int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j) - '0';
}
}
Temp147bb obj = new Temp147bb(n, m, map);
obj.bfs();
}
}
class Temp147bb{
int [][]map;//处理后的地图（包含每个点是否可以走）
int [][]path;//标志地图中可走的每点是否已经访问
int n;//地图实际行数
int m;//地图实际列数
int []dx = {1, 0, 0, -1};//下 左 右 上
int []dy = {0, -1, 1, 0};
char []c = new char[] {'D', 'L', 'R', 'U'};//按字典序搜索
public Temp147bb(int n, int m, int [][]mp) {
this.n = n;
this.m = m;
map = new int[n + 2][m + 2];
path = new int[n + 2][m + 2];
for(int i = 0; i < m + 2; i++) {//处理地图的上下边界
map[0][i] = 1;
map[n + 1][i] = 1;
}
for(int i = 0; i < n + 2; i++) {//处理地图的左右边界
map[i][0] = 1;
map[i][m + 1] = 1;
}
for(int i = 1; i < 1 + n; i++) {//初始化地图
for(int j = 1; j < 1 + m; j++) {
map[i][j] = mp[i - 1][j - 1];
}
}
for(int i = 0; i < n + 2; i++) {
for(int j = 0; j < m + 2; j++) {
path[i][j] = -1;
}
}
path[n][m] = 0;//将入口作为“第0步”
}
public void bfs() {
Queue<Point147bb> qu = new LinkedList<>();
qu.add(new Point147bb(n, m));//起点入队
while(!qu.isEmpty()) {
Point147bb point = qu.poll();
if(point.x == 1 && point.y == 1) {//遍历到终点时，由于是按字典序排序的，可以直接退出
break;
}
for(int i = 0; i < 4; i++) {
int x = point.x + dx[i];//找点的上下左右
int y = point.y + dy[i];
if(map[x][y] == 0 && path[x][y] == -1) {//目标点合法且未被遍历
qu.add(new Point147bb(x, y));
path[x][y] = path[point.x][point.y] + 1;//下一步为上个点步数加一
}
}
}
System.out.println(path[1][1]);//该点为总步数
StringBuilder ans = new StringBuilder();
Point147bb point = new Point147bb(1, 1);//从起点开始
for(int i = 0; i < 4; i++) {//遍历步数，得到路径
int x = point.x + dx[i];
int y = point.y + dy[i];
if(path[x][y] != -1 && path[x][y] == path[point.x][point.y] - 1) {//还需保证合法点
ans.append(c[i]);
point = new Point147bb(x, y);
i = -1;//使进行下一趟查找
}
}
System.out.println(ans);
}
}
class Point147bb{//坐标信息
int x;
int y;
public Point147bb(int x, int y) {
this.x = x;
this.y = y;
}
}提交截图：
?
java代码：（将路径封装进类求路径）（推荐）
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int [][]map = new int[n][m];
for(int i = 0; i < n;i++) {
String str = br.readLine();
for(int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j) - '0';
}
}
Temp147b obj = new Temp147b(n, m, map);
obj.bfs();
}
}
class Temp147b{
int [][]map;//处理后的地图（包含每个点是否可以走）
boolean [][]vis;//标志地图中可走的每点是否已经访问
int n;//地图实际行数
int m;//地图实际列数
Point147b start = new Point147b(1, 1, 0, "");
int []dx = {1, 0, 0, -1};//下 左 右 上
int []dy = {0, -1, 1, 0};
char []c = new char[] {'D', 'L', 'R', 'U'};//按字典序搜索
public Temp147b(int n, int m, int [][]mp) {
this.n = n;
this.m = m;
map = new int[n + 2][m + 2];
vis = new boolean[n + 2][m + 2];
vis[1][1] = true;//将入口置为已访问
for(int i = 0; i < m + 2; i++) {//处理地图的上下边界
map[0][i] = 1;
map[n + 1][i] = 1;
}
for(int i = 0; i < n + 2; i++) {//处理地图的左右边界
map[i][0] = 1;
map[i][m + 1] = 1;
}
for(int i = 1; i < 1 + n; i++) {//初始化地图
for(int j = 1; j < 1 + m; j++) {
map[i][j] = mp[i - 1][j - 1];
}
}
}
public void bfs() {
Queue<Point147b> qu = new LinkedList<>();
qu.add(start);
int ansStep = Integer.MAX_VALUE;//存放最终最少步数
String ansPath = "";//最终路径
while(!qu.isEmpty()) {
Point147b point = qu.poll();
int x = point.x;
int y = point.y;
if(x == n && y == m) {//已经首先访问到出口（按字典序）
if(point.step < ansStep) {
ansStep = point.step;
ansPath = point.path;
}
break;
}
for(int i = 0; i < 4; i++) {//访问该点的上下左右
int tx = x + dx[i];
int ty = y + dy[i];
if(map[tx][ty] == 0 && !vis[tx][ty]) {//该点合法且还未被访问
qu.add(new Point147b(tx, ty, point.step + 1, point.path + c[i]));
vis[tx][ty] = true;//置为已访问
}
}
}
System.out.println(ansStep);
System.out.println(ansPath);
}
}
class Point147b{//坐标信息
int x;
int y;
int step;//走到该点时的步数
String path;//走到该点的路径
public Point147b(int x, int y, int step, String path) {
this.x = x;
this.y = y;
this.step = step;
this.path = path;
}
}提交截图：
比较dfs和bfs：
dfs因为可以回溯，所以会得到所有可能的路径解，即可能到达终点的路径的总数。但前提是数据规模不能太大。
bfs会用到队列，不会用到栈，所以不需要考虑“溢出”的问题，对数据的规模可以放宽。但由于不能回溯，最终只能得到一种解，无法求出总数。