我有一个很大的开放式迷宫,像这样:
############################################################
# .....................#...#................#.........#.....#
# ..##.......x.........#.#.#...#.........x..#......#..#.....#
# ...#.......#....#....#.#.#...#...####.....####...#..#####.#
# .....###...#....#....###.#...#.........#.........#......#.#
#### .#..#...#....#........#...#####..#..#...#######..##..#.#
# ....##.....#....#................#..####......#...........#
# ......##...######........x....................#......######
# ....##........................................#...........#
# .........##########...############........#...#...####....#
# .....#...#..#..#..#......#.......#........#...#....###....#
####### ...#..#..#..#......#.......#.....####...............#
# .....#...#..#..#..#......#.......#........................#
# .....#####..#..#..#......#.......######............x......#
# .........................#................................#
# ..................x......#..##..........#####.............#
# .........................####.............................#
# ..........................................................#
# ....##.....#....#................#..####......#...........#
# .....s##...######.............................#......######
# ....##........................................#...........#
# .........##########...############........#...#...####....#
# .....#...#..#..#..#......#.......#........#...#....###....#
####### ...#..#..#..#......#.......#...x.####...............#
# .....#...#..#...x.#......#.......#.................#......#
# .....#####..#..#..#...#..###....#######............######.#
# ...............#..x...#..#.....##...........####...#......#
# ...............#......#.........#.........##...#..........#
# ...............#......#.........#..........#............#.#
############################################################
“s”是起点。并且有多个目的点“x”。我只需要找到一个目的地。如果目标接近起点,bfs算法可以很快找到解决方案。如果他们像上面的例子那样离得更远,那就需要无尽的时间。所以我的问题是:a)这个算法对这种特定类型的迷宫不好,我应该用a*或者类似的东西吗。b) 我的执行不好吗?
实施:
public class BFS {
public static String getPath(String[][] map) {
String[] ways = { "L", "R", "U", "D" }; // directions to go
Queue<String> q = new LinkedList<>();
q.offer("");
String path = "";
while (!foundBait(map, path)) {
path = q.poll();
for (String s : ways) {
String newPath = path + s;
if (valid(map, newPath))
q.offer(newPath);
}
}
return path;
}
private static boolean foundBait(String[][] map, String moves) {
int xStart = 0;
int yStart = 0;
for (int y = 0; y < map.length; y++)
for (int x = 0; x < map[0].length; x++)
if (map[y][x].equals("s")) {
xStart = x;
yStart = y;
}
int i = xStart;
int j = yStart;
for (int s = 0; s < moves.length(); s++) {
if (moves.charAt(s) == "L".charAt(0))
i--;
else if (moves.charAt(s) == "R".charAt(0))
i++;
else if (moves.charAt(s) == "U".charAt(0))
j--;
else if (moves.charAt(s) == "D".charAt(0))
j++;
}
if (map[j][i].equals("x"))
return true;
return false;
}
private static boolean valid(String[][] map, String moves) {
int xStart = 0;
int yStart = 0;
for (int y = 0; y < map.length; y++)
for (int x = 0; x < map[0].length; x++)
if (map[y][x].equals("s")) {
xStart = x;
yStart = y;
}
int i = xStart;
int j = yStart;
for (int s = 0; s < moves.length(); s++) {
if (moves.charAt(s) == "L".charAt(0))
i--;
else if (moves.charAt(s) == "R".charAt(0))
i++;
else if (moves.charAt(s) == "U".charAt(0))
j--;
else if (moves.charAt(s) == "D".charAt(0))
j++;
if (!(0 <= i && i < map[0].length && 0 <= j && j < map.length))
return false;
else if (map[j][i].equals("#") || map[j][i].equals("-"))
return false;
}
return true;
}
}
1条答案
按热度按时间f5emj3cl1#
如注解中所述,问题不是标记添加到路径中的节点,解决方法是使用第二个矩阵进行标记。