- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
所以我的任务是创建一个迷宫解算器,其中包含一个队列、一个集合、一个位置对象和最终形成一个迷宫对象的单元格对象。
快速浏览一下我完成后所有代码的基本功能:
7
10
_ _ _ _ _ _ _ _ _
|_ _ _ | _ _ _ |
| _ _| | | _ | |
| | | |_| | | |_| |
|_ _|_ _ _| |_ | |
| _ | | _ _| |_|
| |_ _| _| |_ |
|_ _ _ _|_ _|_ _ _| |
进入这个:
@ _ _ _ _ _ _ _ _ _
|@ @ @ @| _ _ _ |
| _ _|@| |@ @ @| |
| | |@|_|@| |@|_| |
|_ _|_ @ @ @| |@ @| |
| _ | | _ _|@|_|
| |_ _| _| |_ @ @|
|_ _ _ _|_ _|_ _ _|@|
@
到目前为止,我所做的一切都很好,但是当我开始对迷宫对象中的 findPath() 方法进行实际编码时,我的代码生成了一条无效的路径。当我接收一个文件来读取迷宫时,我将该迷宫转换为一个多维字符数组,然后将该字符数组转换为一个多维单元格数组,并将每个单元格的北、南、东、西边界映射为 boolean 值。
现在要真正弄清楚如何在迷宫中导航,我曾在 Maze 的 findPath() 方法中尝试过,但实际上有点失败。
@ @ @ @ . . . . . .
. . . @ . . . . . .
. @ @ @ . . . . . .
. @ @ @ @ . . . . .
. . @ @ @ . . . . .
. @ @ @ @ . . . . .
. . . . . . . . . .
首先,为了说明我应该实现的目标,让我让您看一下我的需求文档:
The algorithm operates according to the following pseudo-code:
* Visit the starting Location.
* Add this Location to the set.
* Enqueue the Location in the queue.
while (ArrayQueue<E> != empty( ))
{
Dequeue a Location(next) from the queue
For each neighbor of Location(next) which has
not yet been placed in the set, repeat:
* Visit the neighbor of Location(next).
* Add the neighbor of Location(next) to the Set.
* Enqueue the neighbor of Location(next)in the Queue.
}
我几乎可以肯定我在某种程度上正确地使用了他的算法,但我无法弄清楚我做错了什么以获得我遇到的路径。我最头疼的是我在下面包含的 Maze 对象的 findPath() 方法。我想我最大的问题是我做错了什么?我已经在这里待了好几天了,只是想不通。任何帮助表示赞赏。我的代码如下:
My Maze 的查找路径方法
public void findPath()
{
Location startLocation = new Location(0, 0);
theMaze[startLocation.getRow()][startLocation.getColumn()].setVisited(true);
Location endLocation = new Location(6, 9);
Location cursor;
locationQueue.enqueue(startLocation);
locationSet.enter(startLocation);
while(!locationQueue.isEmpty())
{
cursor = locationQueue.dequeue();
if(cursor == endLocation)
break;
for(int i = 0; i < 4; i++)
{
Location temp = cursor.getLoc(i);
if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
{
cursor = cursor.getLoc(i);
theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);
if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
{
cursor = startLocation;
continue;
}
locationSet.enter(cursor);
locationQueue.enqueue(cursor);
}
}
}
for(int i = 0; i < locationSet.size(); i++)
{
System.out.println("Row " + locationSet.get(i).getRow() + " Column " + locationSet.get(i).getColumn());
theMaze[locationSet.get(i).getRow()][locationSet.get(i).getColumn()].setPath();
}
for(int i = 0; i < theMaze.length; i++)
{
for(int j = 0; j < theMaze[i].length; j++)
{
System.out.print(theMaze[i][j].toString());
}
System.out.print("\n");
}
}
编辑:我的问题出在 Maze 对象上,而不是其他类,所以我基本上是在清理。
最佳答案
您的基本算法存在缺陷。您只需将单元格添加到路径中,但如果它们变成死胡同,则不要删除它们。
这类问题最适合递归算法。
function findExit(gameMap, listOfVisitedCells, currentCell, solution)
listOfVisitedCells.add(currentCell);
for each gameMap.NeighbourOf(currentCell)
if neighbour not in listOfVisitedCells
solution.add(neighbour)
if (gameMap.isExit(neighbour)) {
return true;
}
if (findExit(gameMap, listOfVisitedCells, currentCell, solution)) {
return true;
}
solution.remove(neighbour);
}
}
// No neighbours of the current cell got to find the exit.
return false;
}
当然,这将以深度优先的方式探索 map ,因此如果有多条路径有效,则不能保证找到最短的路径(为此使用 Djikstra 算法)。
更新:通过审查您的代码:
很难在头脑中调试这么多行代码,并且 SO 不能代替您花费大量时间使用您选择的调试器,观察程序的实际状态与预期状态,等等。不要期望太多,SO 更适合于代码量有限的具体问题(“我希望这段代码能做到这一点,但它没有,为什么”)。
无论如何,这让我觉得很奇怪:
Location temp = cursor.getLoc(i);
if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
{
cursor = cursor.getLoc(i); <-- Why are you overwritting the current
<-- location when you have still not checked
<-- all the posible directions?
theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);
if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
{
cursor = startLocation;
continue;
}
locationSet.enter(cursor);
locationQueue.enqueue(cursor);
}
我敢打赌这是不正确的。当然,可能还隐藏着其他问题,最好是自己调试一下,找到没有按预期工作的片段(然后,如果需要,在SO中寻求帮助)。
关于Java Maze Solver - 我从来没有这么卡过,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15807137/
我是一名优秀的程序员,十分优秀!