我很难将提示给我们的算法转化为可用的代码。我们得到了一个方向枚举，它有8个坐标(N，NE，NW，S，SE.SW.E，W)和出口HERE。
这是暗示的算法：
getPathToExit(row, col):
if (row, col) is outside of the map:
return an empty list
else if (row, col) is an obstacle:
return an empty list
else if (row, col) is marked as visited or as deadend:
return an emtpy list
else if (row, col) is the exit:
//optional: mark exit as visited
return a list containing Direction.HERE
else:
//try to find a path from current square to exit:
mark current square as visited (that is, part of path)
for each neighbor of current square:
path = path from neighbor to exit
if path is not empty:
add (direction to neighbor) to start of path
return path
//after for loop: no path exists from this square to exit
mark current square as deadend
return empty list
这是我已经工作了一段时间的代码：
public java.util.ArrayList<Direction> getPathToExit(){
for (int x=0; x<map.length; x++){
for (int y=0; y<map[x].length; y++){
if (map[x][y]=='S'){
this.startRow=x;
this.startCol=y;
}
}
}
System.out.println("start "+startRow+", "+startCol);
return getPathToExit(this.startRow, this.startCol);
}
private java.util.ArrayList<Direction> getPathToExit(int row, int col){
Direction [] dirs = Direction.values();
ArrayList<Direction> path = new ArrayList<Direction>();
getPathToExit(row, col);
if (row < 0 || col < 0 || row > map.length || col > map[row].length){
return null;
}
else if (map[row][col] != ' '){
return null;
}
else if (map[row][col] == 'E'){
path.add(Direction.HERE);
return path;
}
else {
for (int x=0; x<dirs.length-1; x++){
int nextRow = row + dirs[x].getRowModifier();
int nextCol = col + dirs[x].getColModifier();
path = getPathToExit(nextRow, nextCol);
}
}
return path;
}
这是枚举类：
public enum Direction {
N, NE, E, SE, S, SW, W, NW, HERE;
/**
* Returns the X/column change on the screen that is associated with
* this direction: -1 for W, 0 for N/S, and +1 for E.
*/
public int getColModifier() {
int mod;
switch (this) {
case NW:
case W:
case SW:
mod = -1;
break;
case NE:
case E:
case SE:
mod = +1;
break;
default:
mod = 0;
break;
}
return mod;
}
/**
* Returns the Y/row change on the screen that is associated with
* this direction: -1 for N, 0 for E/W, and +1 for south.
*/
public int getRowModifier() {
int mod;
switch (this) {
case N:
case NE:
case NW:
mod = -1;
break;
case S:
case SE:
case SW:
mod = +1;
break;
default:
mod = 0;
break;
}
return mod;
}
/** As {@link #getColModifier()} */
public int getXModifier() {
return this.getColModifier();
}
/** As {@link #getRowModifier()} */
public int getYModifier() {
return this.getRowModifier();
}
/**
* Returns the direction that is the opposite of this one.
* For example, <code>Direction.NE.reverse() == Direction.SW</code>.
* (The opposite of HERE is still HERE though.)
*/
public Direction reverse() {
if (this == HERE) {
return this;
}else {
int reversed = (this.ordinal() + 4) % 8;
Direction[] dirs = Direction.values();
return dirs[reversed];
}
}
}
提前谢谢。
代码中有两个问题：
(1)在主for循环中：
for (int x=0; x<dirs.length-1; x++){
int nextRow = row + dirs[x].getRowModifier();
int nextCol = col + dirs[x].getColModifier();
path = getPathToExit(nextRow, nextCol);
}
您需要检查递归调用：getPathToExit()是否返回了一个非空列表。如果有，您应该break循环，并将相关方向推到它的起点。你已经找到了一条路-不点继续检查其余的！
(2)为了使您的算法完整(如果存在解决方案，请找到解决方案)，您需要维护visited集，并避免重新访问已访问的节点。
看看下面的例子：
-------
|S |x1|
-------
|x2|E |
-------
其中所有都是有效的正方形(没有障碍物)，S是起点，E是终点。
现在，假设方向的顺序是right,left, ...。
代码(未设置visited)将执行以下操作：
go right (to x1).
go right - out of maze, go back.
go left (to S).
go right (to x1).
go right - out of maze, go back.
go left (to S)
....
你处于一个无限循环中！(DFS的一个已知撤回)
StackOverflowError通常表明这是问题所在，所有递归调用的调用堆栈都已满，并引发错误。
要解决此问题，需要维护一个visited集，并避免重新访问已访问的节点。有了这个集合，上面的迷宫(方向顺序是right, left, down, ...)会发生什么：
go right (to x1)
go right - out of maze, go back.
go left (to S) - already visitted, go back.
go down (to E) - found target, return it.
一个更高级的替代方案是使用迭代深化DFS，这基本上意味着，将路径的长度限制为l，并迭代增加该l。这次我会忽略这个替代方案，它更先进一点。
顺便说一句，你的算法是DFS的一种实现，它是由访问集和有限图组成的(如果存在，总是能找到解决方案)，但不是最优的(不能保证找到最短路径)。要查找最短路径，您可能需要使用BFS。
还有：我假设该方法第三行中的递归调用是用于调试的剩余部分。它不应该在那里。