- 深度优先搜索
一条路走到黑，回溯 - 广度优先搜索
一石激起千层浪
一、走迷宫问题，只有一条路
1. 题目描述
题目链接
2. 题目分析 + 加解决方法
- 新建Pos（x，y）类，表示位置
- List< Pos >保存各个位置
- boolean[][] 标记数组，标记位置是否走过
import java.util.*;
public class Main {
static class Pos{
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[][] nextP = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt();
int col = scanner.nextInt();
int[][] map = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
map[i][j] = scanner.nextInt();
}
}
boolean[][] book = new boolean[row][col];
List<Pos> results = DFS(map, row, col, new ArrayList<>(), book, 0, 0);
for (Pos pos : results) {
System.out.println("(" + pos.x + "," + pos.y + ")");
}
}
public static List<Pos> DFS(int[][] map, int row, int col, List<Pos> results, boolean[][] book, int x, int y){
if(x < 0 || x >= row || y < 0 || y >= col || book[x][y]){
return results;
}
if(map[x][y] == 1){
return results;
}
results.add(new Pos(x, y));
book[x][y] = true;
if(x == row - 1 && y == col - 1){
return results;
}
for (int[] next : nextP) {
int newX = x + next[0];
int newY = y + next[1];
DFS(map, row, col, results, book, newX, newY);
if(book[row - 1][col - 1]){
return results;
}
}
results.remove(results.size() - 1);
return results;
}
}
二、走迷宫之最短路径（多条路找最短路径）
1. 题目描述
题目链接
2. 题目分析 + 解决方法
多条路径找最短路径
通过一条路径走到终点，可能并不是最短路径；因此到达终点后，需要回退到前面的位置，继续寻找其他路径，通过比较，找到最短路径
import java.util.*;
public class Main {
static class Pos{
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[][] nextP = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt();
int col = scanner.nextInt();
int[][] map = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
map[i][j] = scanner.nextInt();
}
}
boolean[][] book = new boolean[row][col];
List<Pos> path = new ArrayList<>();
List<Pos> minPath = new ArrayList<>();
getMinPath(map, row, col, 0 ,0, path, minPath, book);
for (Pos pos : minPath) {
System.out.println("(" + pos.x + "," + pos.y + ")");
}
}
public static void getMinPath(int[][] map, int row, int col, int x, int y, List<Pos> path, List<Pos> minPath, boolean[][] book){
// 1. 判断是否越界，是否走过，是否是障碍
if(x < 0 || x >= row || y < 0 || y >= col || book[x][y] || map[x][y] == 1){
return;
}
// 2. 没有越界，添加这个位置，并标记这个位置走过
path.add(new Pos(x, y));
book[x][y] = true;
// 3. 判断是否到达终点
if(x == row - 1 && y == col - 1){
// 到达终点，更新 minPath
if(minPath.isEmpty() || minPath.size() > path.size()){
minPath.clear();
minPath.addAll(path);
}
} else {
// 没有到达终点，继续向四个方向搜索
for (int[] next : nextP) {
int newX = x + next[0];
int newY = y + next[1];
getMinPath(map, row, col, newX, newY, path, minPath, book);
}
}
// 4. 回溯
path.remove(path.size() - 1);
book[x][y] = false;
}
}
三、走迷宫之最短路径，多条路找最短步数
1. 题目描述
题目链接
2. 题目分析 + 解决
站在某个位置，搜索的顺序应该是 下、右、左、上（深搜时要注意，广搜时无所谓）
- 深度优先搜索（DFS）
深度优先搜索，一条路走到黑，只一条路走到终点
如果只走一条路到达终点，我们不知道这条路是不是最短的路径
可以多次进行DFS
- 一条路线走到终点，不要结束
- 回溯，再通过其他的路线走到终点，记录路线长度
- 直到所有的路线走完，比较不同路线，得出最短的路线
错误示例：
标记数组标记遍历过的位置，后续不在遍历了，这是不可行的
- 如上图，(5,6)位置，第一条路线走过，标记（5,6）位置；第二条路线走过时，遇到（5,6）不走了，就尬住了
- 但是如果不标记的话，死循环
- 所以回溯的时候一定要记得将走过的路径标记为“未走过”
时间复杂度过高，可通过部分测试用例
public class Main {
static int[][] nextP = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[][] map = new char[10][10];
while(scanner.hasNext()){
for (int i = 0; i < 10; i++) {
String str = scanner.nextLine();
for (int j = 0; j < 10; j++) {
map[i][j] = str.charAt(j);
}
}
List<Integer> steps = new ArrayList<>();
boolean[][] book = new boolean[10][10];
getMinStep(map, -1, steps, 0, 1, book);
int min = Integer.MAX_VALUE;
for (int val : steps) {
min = Math.min(min, val);
}
System.out.println(min);
}
}
public static void getMinStep(char[][] map, int step, List<Integer> steps, int x, int y, boolean[][] book){
if(x < 0 || x >= 10 || y < 0 || y >= 10 || map[x][y] == '#' || book[x][y]){
return;
}
step++;
book[x][y] = true;
if(x == 9 && y == 8){
steps.add(step);
} else {
for (int[] next : nextP) {
int newX = x + next[0];
int newY = y + next[1];
getMinStep(map, step, steps, newX, newY, book);
}
}
book[x][y] = false;
}
}
解决方法：
使用 array[i][j] 表示 走到（i，j）的步数
- 将array[i][j] 除起点位置，均赋值 MAX_VALUE
- 在（i，j）位置搜索时，搜索其四个方向（下、右、左、上）；
如果 array[newI][newJ] > array[i][j] + 1（此处注意，没有“=”，如果有“=”，重走老路了），说明到达此位置有更短的路径；
更新array[newI][newJ]，进入此位置继续搜索。
public class Main {
static int[][] nextP = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[][] map = new char[10][10];
while(scanner.hasNext()){
for (int i = 0; i < 10; i++) {
String str = scanner.nextLine();
for (int j = 0; j < 10; j++) {
map[i][j] = str.charAt(j);
}
}
int[][] path = new int[10][10];
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
path[i][j] = Integer.MAX_VALUE;
}
}
getMinPath(map, path, 1, 1, 0, 1);
System.out.println(path[9][8]);
}
}
public static void getMinPath(char[][] map, int[][] path, int x, int y, int preX, int preY){
if(x < 0 || x >= 10 || y < 0 || y >= 10 || map[x][y] == '#'){
return;
}
if(path[x][y] <= path[preX][preY] + 1){
return;
}
path[x][y] = path[preX][preY] + 1;
for (int[] next : nextP) {
int newX = x + next[0];
int newY = y + next[1];
getMinPath(map, path, newX, newY, x, y);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[][] chars = new char[10][10];
while(scanner.hasNext()){
for (int i = 0; i < 10; i++) {
String str = scanner.nextLine();
for (int j = 0; j < 10; j++) {
chars[i][j] = str.charAt(j);
}
}
int[][] nextP = {{0,1},{1,0},{0,-1},{-1,0}};
int[][] path = new int[10][10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
path[i][j] = Integer.MAX_VALUE;
}
}
path[0][1] = 0;
DFS(chars, path, nextP, 0, 1);
System.out.println(path[9][8]);
}
}
public static void DFS(char[][] chars, int[][] path, int[][] nextP, int x, int y){
for (int[] next : nextP) {
int newX = x + next[0];
int newY = y + next[1];
if(newX < 0 || newX > 9 || newY < 0 || newY > 9){
continue;
}
if(chars[newX][newY] == '#'){
continue;
}
// 此处一定要有 =，如果没有 =，会重走老路
if(path[newX][newY] <= path[x][y] + 1){
continue;
}
path[newX][newY] = path[x][y] + 1;
DFS(chars, path, nextP, newX, newY);
}
}
- 广度优先搜索（BFS）
- 站在（0,1）的位置上，搜索其 “下 右 左 上” 四个方向，走1步可以到达（1,1），即到达（1,1）位置的最短路程就是1步
- 再站在（1,1）的位置上，搜索四个方向，走2步就可以到达（2,1）（1,2），即到达（2,1）（1,2）的最短路程就是2步
- 依次搜索，得到到达（6,6）的最短路程
static class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 迷宫
char[][] map = new char[10][10];
while (scanner.hasNext()) {
for (int i = 0; i < 10; i++) {
String str = scanner.nextLine();
for (int j = 0; j < 10; j++) {
map[i][j] = str.charAt(j);
}
}
// 方向数组
int[][] nextP = {{-1,0},{1,0},{0,-1},{0,1}};
// 标记数组，为true表示这个位置搜索过了；为false表示未搜索过，可以入队
boolean[][] book = new boolean[10][10];
Queue<Pair> queue = new LinkedList<>();
Pair start = new Pair(0,1);
queue.offer(start);
book[0][1] = true;
// 计数器
int count = 0;
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
Pair pair = queue.poll();
size--;
for (int[] next : nextP) {
int newX = pair.x + next[0];
int newY = pair.y + next[1];
if(newX < 0 || newX >= 10 || newY < 0 || newY >= 10){
continue;
}
if(map[newX][newY] == '#'){
continue;
}
if(book[newX][newY]){
continue;
}
queue.offer(new Pair(newX, newY));
book[newX][newY] = true;
}
}
if(!queue.isEmpty()){
count++;
}
// 如果终点位置(9,8) 为true，表示已经搜索到了终点位置，得到到达终点的最短路径count
if(book[9][8]){
System.out.println(count);
break;
}
}
}
}
孔孟之乡，运河之都，文化济宁
山东济宁
本文含有隐藏内容，请 开通VIP 后查看