题解 | #走迷宫#
走迷宫
http://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64
深度优先遍历
用例通过率: 30%
思路:
通过回溯法，找到起点到终点的 所有 路径。然后，在所有路径中取 最小 的那一个。这种方法仅适用于迷宫 比较小 的时候。如果迷宫很大，大概率 超时了! 事实上，深度优先遍历(DFS)就 不太适用于 求最短路径，它一般适用于找 路径的条数。
public static void main(String[] args) {
// 以下代码用于输入数据
Scanner scan = new Scanner(System.in);
String nmStr = scan.nextLine();
int n = Integer.valueOf(nmStr.split(" ")[0]);
int m = Integer.valueOf(nmStr.split(" ")[1]);
String se = scan.nextLine();
int xs = Integer.valueOf(se.split(" ")[0]);
int ys = Integer.valueOf(se.split(" ")[1]);
int xe = Integer.valueOf(se.split(" ")[2]);
int ye = Integer.valueOf(se.split(" ")[3]);
char[][] chrs = new char[n][m];
for (int i = 0; i < n; i++) {
String tmpStr = scan.nextLine();
char[] tmpChar = tmpStr.toCharArray();
for (int j = 0; j < m; j++) {
chrs[i][j] = tmpChar[j];
}
}
if (chrs[xe - 1][ye - 1] == '*') {
System.out.println(-1);
} else {
int res = process(chrs, xs - 1, ys - 1, 0, xe - 1, ye - 1);
System.out.println(res == Integer.MAX_VALUE ? -1 : res);
}
}
public static int process(char[][] chrs, int i, int j, int num, int xe,
int ye) {
if (i == xe && j == ye) {
return num;
}
int n = chrs.length;
int m = chrs[0].length;
if (i < 0 || i >= n || j < 0 || j >= m || chrs[i][j] == '*') {
return Integer.MAX_VALUE;
}
chrs[i][j] = '*';
num++;
int up = process(chrs, i - 1, j, num, xe, ye);
int down = process(chrs, i + 1, j, num, xe, ye);
int left = process(chrs, i, j - 1, num, xe, ye);
int right = process(chrs, i, j + 1, num, xe, ye);
// 回溯
chrs[i][j] = '.';
num--;
return Math.min(up, Math.min(down, Math.min(left, right)));
}
广度优先遍历
用例通过率: 100%
思路:
广度优先遍历，是一种 层次遍历。它从 起点 开始，从上往下、从左到右 进行遍历。这种层次遍历，可以确保起点到终点的路径是 最短的。最坏情况下，也就是将所有的节点遍历一次，才能找到 终点。但是呢，广度优先遍历不太适用于找 路径的条数，归根结底，还是因为一般的 层次遍历，节点只知道自己 当前所在的层次，并不知道自己是由哪一个节点过来的。当然，你可以使用一个 HashMap 来存放每个节点的 上一个节点，但是，对于找 路径数 这种问题来说，并不如 深度优先遍历好。
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] nm = scan.nextLine().split(" ");
int n = Integer.valueOf(nm[0].trim());
int m = Integer.valueOf(nm[1].trim());
String[] se = scan.nextLine().split(" ");
int xs = Integer.valueOf(se[0].trim()) - 1;
int ys = Integer.valueOf(se[1].trim()) - 1;
int xe = Integer.valueOf(se[2].trim()) - 1;
int ye = Integer.valueOf(se[3].trim()) - 1;
char[][] matrix = new char[n][m];
for (int i = 0; i < n; i++) {
char[] chrs = scan.nextLine().toCharArray();
for (int j = 0; j < chrs.length; j++) {
matrix[i][j] = chrs[j];
}
}
if (xs == xe && ys == ye) {
System.out.println(0);
return;
}
int[][] steps = new int[n][m];
steps[xs][ys] = 0;
Queue<int[]> queue = new LinkedList<>();
int[] tmp = new int[] {xs, ys};
queue.add(tmp);
while (!queue.isEmpty()) {
tmp = queue.poll();
if (tmp[0] == xe && tmp[1] == ye) {
break;
}
if (tmp[0] - 1 >= 0 && tmp[0] - 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] - 1][tmp[1]] == '.') {
int[] location = new int[] {tmp[0] - 1, tmp[1]};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0] - 1][tmp[1]] = '*';
}
if (tmp[0] + 1 >= 0 && tmp[0] + 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] + 1][tmp[1]] == '.') {
int[] location = new int[] {tmp[0] + 1, tmp[1]};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0] + 1][tmp[1]] = '*';
}
if (tmp[0] >= 0 && tmp[0] < n && tmp[1] - 1 >= 0 && tmp[1] - 1 < m && matrix[tmp[0]][tmp[1] - 1] == '.') {
int[] location = new int[] {tmp[0], tmp[1] - 1};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0]][tmp[1] - 1] = '*';
}
if (tmp[0] >= 0 && tmp[0] < n && tmp[1] + 1 >= 0 && tmp[1] + 1 < m && matrix[tmp[0]][tmp[1] + 1] == '.') {
int[] location = new int[] {tmp[0], tmp[1] + 1};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0]][tmp[1] + 1] = '*';
}
}
System.out.println(steps[xe][ye] == 0 ? -1 : steps[xe][ye]);
}
总结:
对于一道问题，到底是使用 深度优先遍历 还是 广度优先遍历，到底是求 路径数 还是 最短路径，不要混。我们应该要发挥这两种 遍历算法 的优势，清楚它们之间的区别。(新手见解)
完整代码如下:
import java.util.*;
public class Main {
/**********************************************************************************/
// 深度优先遍历 用例通过率: 30%
// 思路: 通过回溯法，找到起点到终点的所有路径，然后，在所有路径中取最小的那一个。这种方法仅适用于迷宫比较小的时候。如果迷宫很大，肯定超时了!事实上，深度优先遍历(DFS)就不太适合于，在所有路径中，找到路径最短的，它一般适用于找到底有多少种路径。
/*
public static void main(String[] args) {
// 以下代码用于输入数据
Scanner scan = new Scanner(System.in);
String nmStr = scan.nextLine();
int n = Integer.valueOf(nmStr.split(" ")[0]);
int m = Integer.valueOf(nmStr.split(" ")[1]);
String se = scan.nextLine();
int xs = Integer.valueOf(se.split(" ")[0]);
int ys = Integer.valueOf(se.split(" ")[1]);
int xe = Integer.valueOf(se.split(" ")[2]);
int ye = Integer.valueOf(se.split(" ")[3]);
char[][] chrs = new char[n][m];
for (int i = 0; i < n; i++) {
String tmpStr = scan.nextLine();
char[] tmpChar = tmpStr.toCharArray();
for (int j = 0; j < m; j++) {
chrs[i][j] = tmpChar[j];
}
}
if (chrs[xe - 1][ye - 1] == '*') {
System.out.println(-1);
} else {
int res = process(chrs, xs - 1, ys - 1, 0, xe - 1, ye - 1);
System.out.println(res == Integer.MAX_VALUE ? -1 : res);
}
}
public static int process(char[][] chrs, int i, int j, int num, int xe,
int ye) {
if (i == xe && j == ye) {
return num;
}
int n = chrs.length;
int m = chrs[0].length;
if (i < 0 || i >= n || j < 0 || j >= m || chrs[i][j] == '*') {
return Integer.MAX_VALUE;
}
chrs[i][j] = '*';
num++;
int up = process(chrs, i - 1, j, num, xe, ye);
int down = process(chrs, i + 1, j, num, xe, ye);
int left = process(chrs, i, j - 1, num, xe, ye);
int right = process(chrs, i, j + 1, num, xe, ye);
// 回溯
chrs[i][j] = '.';
num--;
return Math.min(up, Math.min(down, Math.min(left, right)));
}
*/
/**********************************************************************************/
// 广度优先遍历 用例通过率: 100%
// 思路: 广度优先遍历，更像是一种”层次扩散“。它从起点开始，一层一层往下进行遍历(”扩散“)，那么，就可以确保起点到终点的路径最短。但是呢，广度优先遍历不太适用于找有多少条路径。因为你是类似”层级“的遍历，你只知道你的上一层是多少，但是，你并不知道你的父节点是谁。
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] nm = scan.nextLine().split(" ");
int n = Integer.valueOf(nm[0].trim());
int m = Integer.valueOf(nm[1].trim());
String[] se = scan.nextLine().split(" ");
int xs = Integer.valueOf(se[0].trim()) - 1;
int ys = Integer.valueOf(se[1].trim()) - 1;
int xe = Integer.valueOf(se[2].trim()) - 1;
int ye = Integer.valueOf(se[3].trim()) - 1;
char[][] matrix = new char[n][m];
for (int i = 0; i < n; i++) {
char[] chrs = scan.nextLine().toCharArray();
for (int j = 0; j < chrs.length; j++) {
matrix[i][j] = chrs[j];
}
}
if (xs == xe && ys == ye) {
System.out.println(0);
return;
}
int[][] steps = new int[n][m];
steps[xs][ys] = 0;
Queue<int[]> queue = new LinkedList<>();
int[] tmp = new int[] {xs, ys};
queue.add(tmp);
while (!queue.isEmpty()) {
tmp = queue.poll();
if (tmp[0] == xe && tmp[1] == ye) {
break;
}
if (tmp[0] - 1 >= 0 && tmp[0] - 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] - 1][tmp[1]] == '.') {
int[] location = new int[] {tmp[0] - 1, tmp[1]};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0] - 1][tmp[1]] = '*';
}
if (tmp[0] + 1 >= 0 && tmp[0] + 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] + 1][tmp[1]] == '.') {
int[] location = new int[] {tmp[0] + 1, tmp[1]};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0] + 1][tmp[1]] = '*';
}
if (tmp[0] >= 0 && tmp[0] < n && tmp[1] - 1 >= 0 && tmp[1] - 1 < m && matrix[tmp[0]][tmp[1] - 1] == '.') {
int[] location = new int[] {tmp[0], tmp[1] - 1};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0]][tmp[1] - 1] = '*';
}
if (tmp[0] >= 0 && tmp[0] < n && tmp[1] + 1 >= 0 && tmp[1] + 1 < m && matrix[tmp[0]][tmp[1] + 1] == '.') {
int[] location = new int[] {tmp[0], tmp[1] + 1};
queue.add(location);
steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
matrix[tmp[0]][tmp[1] + 1] = '*';
}
}
System.out.println(steps[xe][ye] == 0 ? -1 : steps[xe][ye]);
}
}
查看9道真题和解析