0
所以我有一個程序,它很好地解決了一個迷宮,並存儲在一個多維整數數組solvedMaze
看起來像什麼是下面的解決方案:通過Java中的迷宮追溯路徑
110111
110101
010100
110100
011100
000000
要指出其中開始和結束是:
public List<Location> solution() {
int[][] solvedMaze = new int[height][width];
Location current;
PriorityQueue<Location> queue = new PriorityQueue<>(new Comparator<Location>() {
@Override
public int compare(Location a, Location b) {
double distanceA = distance(start, a)/1.5 + distance(a, end);
double distanceB = distance(start, b)/1.5 + distance(b, end);
return Double.compare(distanceA, distanceB);
}
private double distance(Location first, Location second) {
return Math.abs(first.i() - second.i()) + Math.abs(first.j() - second.j());
}
});
queue.add(start);
while ((current = queue.poll()) != null) {
if (solvedMaze[current.i()][current.j()] != 0) {
continue;
}
int mod = 1;
for (Location next : new Location[]{
current.south(), current.west(), current.north(), current.east()
}) {
if (isInMaze(next) && isClear(next)) {
if (solvedMaze[next.i()][next.j()] == 0) {
queue.add(next);
} else {
mod = Math.min(solvedMaze[next.i()][next.j()], mod);
}
}
}
solvedMaze[current.i()][current.j()] = mod;
if (isFinal(current)) {
break;
}
}
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
System.out.print(solvedMaze[i][j]);
}
System.out.println();
}
if (solvedMaze[end.i()][end.j()] != 0) {
List<Location> route = new ArrayList<>();
Location temp = end;
while (!temp.equals(start)) {
route.add(temp);
Location best = null;
int bestNumber = solvedMaze[temp.i()][temp.j()];
for (Location next : new Location[]{
temp.north(), temp.south(), temp.west(), temp.east()
}) {
if (isInMaze(next) && solvedMaze[next.i()][next.j()] != 0) {
if (solvedMaze[next.i()][next.j()] < bestNumber) {
bestNumber = solvedMaze[next.i()][next.j()];
best = next;
}
}
}
assert best != null;
temp = best;
}
route.add(start);
Collections.reverse(route);
return route;
} else {
return null;
}
}
:
S10111
11010E
010100
110100
011100
000000
我必須既解決和回掃一個迷宮的路徑的代碼如下給出
其中Location
是一個包含x和y座標的類,並且start
和end
是位置。由於某種原因,我的輸出始終是null
,我不知道爲什麼。在調試一些簡單的print
之後,我發現從未輸入回掃邏輯中的solvedMaze[next.i()][next.j()] < bestNumber
條件。這個方法有什麼問題?有沒有更好的(更有效的)方法來解決它?
我改變了問題以包括整個方法;它既解決了迷宮又回到了步驟。希望它現在應該更清楚! – T145
這有幫助嗎? – T145