1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
package com.eh.ftd.dsa.ds;
import java.util.LinkedList;
import java.util.Queue;
/**
* todo
*
* @author David Li
* @create 2020/06/30 22:57
*/
public class Maze1 {
// 迷宫
private char[][] maze;
// 4个方向
int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 是否走过
boolean[][] visited;
// 记录走到当前坐标的上一坐标
Pos[][] pre;
static class Pos {
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
public Maze1(char[][] maze) {
this.maze = maze;
this.visited = new boolean[maze.length][maze[0].length];
this.pre = new Pos[maze.length][maze[0].length];
}
/**
* 寻找迷宫最短路径
*
* @param start
*/
public Pos bfs(Pos start) {
Queue<Pos> queue = new LinkedList<>();
// 起点入队
queue.offer(start);
// 当前坐标
Pos cur;
while ((cur = queue.poll()) != null) {
visited[cur.x][cur.y] = true;
// 上下左右试探
for (int i = 0; i < 4; i++) {
int x = cur.x + dir[i][0];
int y = cur.y + dir[i][1];
// 坐标是否在迷宫内部
boolean in = x < maze.length && y < maze[0].length;
if (in && maze[x][y] == 'T') {
// 记录父坐标
pre[x][y] = cur;
// 找到出口
return new Pos(x, y);
}
// 坐标在迷宫内部 && 没被访问过 && 可通行
if (in && !visited[x][y] && maze[x][y] == ' ') {
// 入队
queue.offer(new Pos(x, y));
// 记录父坐标
pre[x][y] = cur;
}
}
}
return null;
}
public void markTheShortestPath(Pos cur) {
// 终点的上一个节点; 不是起点坐标; 上一个节点
for (cur = pre[cur.x][cur.y]; maze[cur.x][cur.y] != 'S'; cur = pre[cur.x][cur.y]) {
// *标记最短通路
maze[cur.x][cur.y] = '.';
}
}
public void printTheShortestPath(Pos cur) {
if (maze[cur.x][cur.y] == 'S') {
System.out.printf("{%d,%d}", cur.x, cur.y);
return;
}
printTheShortestPath(pre[cur.x][cur.y]);
System.out.printf("{%d,%d}", cur.x, cur.y);
}
private void displayMazePath() {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
/**
* 迷宫
* # 挡板
* S 起点
* T 出口
*/
char[][] map = {
{'#', '#', '#', '#', '#', '#', '#', '#', 'T', '#', '#', '#'},
{'#', 'S', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', '#', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', ' ', ' ', '#'},
{'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
};
Maze1 maze = new Maze1(map);
Pos ter = maze.bfs(new Pos(1, 1));
maze.markTheShortestPath(ter);
maze.displayMazePath();
System.out.println("最短路径:");
maze.printTheShortestPath(ter);
}
}
|
