问题描述
所以我们得到了一个迷宫，有墙(W)开放路径(O)、起点(S)和终点(F).
So we are given a maze with walls(W) open path(O) a start pt (S) and a finish pt (F).
我正在尝试编写一个算法，该算法获取迷宫文件，然后将其转换为二维点数组以制作网格.
I am trying to write an algorithm that takes the maze file and then turns it into a 2D array of points to make a grid.
一旦我有了网格，我想从迷宫中的S"字符开始，并尝试找出是否有可能穿过 O 到达 F.(返回布尔值真/假)
Once I have the grid, I want to start on the 'S' character in the maze and try to find whether or not it is possible to traverse through the O's to get to the F. (Return a boolean true/false)
我知道这个迷宫是可以解决的，那么为什么我会得到假"呢??一定有一个复杂的问题，因为我得到的只是简单的布尔错误，而不是对不起，迷宫不可穿越"......
I know that this maze is solvable, so why am I getting 'false'?? There must be a complicate problem because all I get is the plain boolean false, not the "sorry, maze isnt traversable"...
这是 Maze1.txt 文件:
Here is the Maze1.txt file:
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
这是我的代码(新尝试):
Here is my code(new attempt):
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
import java.awt.Point;
public class MazeExplorer {
static Point startPoint = new Point();
static Point finishPoint = new Point();
final static int mazeHeight = 12;
final static int mazeWidth = 58;
static char[][] mazePoints = new char[mazeHeight][mazeWidth];
Stack<Point> pointsNotTraversed = new Stack<Point>();
Point pt = new Point();
static HashSet<Point> previousLocations = new HashSet<Point>();
static Stack<Point> nextPoints = new Stack<Point>();
public static void main(String[] args) throws FileNotFoundException{
System.out.println("Please enter the file name of your Maze");
Scanner console = new Scanner(System.in);
File f = new File(console.nextLine());
Scanner sc = new Scanner(f);
if(!sc.hasNextLine()){
System.out.println("Sorry, please enter a file name with the extension, that contains a maze!");
}
System.out.println("So, you want to know if your maze is solvable.....?");
for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
final String mazeRow = sc.next(); //Get the next row from the scanner.
mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
}
//identify the finish point
for(int i = 0; i < mazeHeight; i++){
for(int j = 0; j<mazeWidth; j++){
if(mazePoints[i][j] == 'F'){
finishPoint = new Point(i, j);
}
}
}
// Identify the start point
for(int i = 0; i< mazeHeight; i++){
for(int j = 0; j < mazeWidth; j++){
if(mazePoints[i][j] == 'S'){
startPoint = new Point(i , j);
}
}
}
isTraversable(startPoint);
}
public static boolean isTraversable(Point current){
boolean isSolvable = false;
do {
mazePoints[current.x][current.y] = ' ';
if (mazePoints[current.y - 1][current.x] == 'O'){ //up dir
nextPoints.push(new Point(current.y - 1, current.x));
mazePoints[current.y - 1][current.x] = ' '; //'X' marks where you've already been
}
if(mazePoints[current.y + 1][current.x] == 'O'){ // below direction
nextPoints.push(new Point(current.y + 1, current.x));
mazePoints[current.y + 1][current.x] = ' ';
}
if(mazePoints[current.y][current.x + 1] == 'O'){ // to the right
nextPoints.push(new Point(current.y, current.x + 1));
mazePoints[current.y][current.x + 1] = ' ';
}
if(mazePoints[current.y][current.x - 1] == 'O'){ // to the left
nextPoints.push(new Point(current.y, current.x - 1));
mazePoints[current.y][current.x - 1] = ' ';
}
if(mazePoints[current.y][current.x] == 'F'){
isSolvable = true;
System.out.println("MAZE IS SOLVABLE, YAHOOOOOO!!!!");
}
current = nextPoints.peek();
nextPoints.pop();
isTraversable(current);
} while(!current.equals('F') && !nextPoints.isEmpty());
return isSolvable;
}
}
推荐答案
算法如下:
do
mark current spot in the array as "visited" (can use any symbol you want)
push all of the neighbors not yet visited onto the stack
current spot <-- top of the stack to visit the next spot
pop the stack
while (exit is not found && stack is not empty)
5 分钟就写完了，如果有错误请告诉我.
Just wrote this in 5 min, let me know if there are bugs.
编辑(关于 OP 的编辑):
EDIT (with respect to OP's edit):
你的canMove方法太复杂了，其实没必要做这样的函数，更不用说查堆栈了.此外，您的 traverseMaze 函数应该在起始位置接受一行和 col 参数，或者您应该将此类信息作为私有变量放入类中.
Your canMove<direction> methods are too complicated, there's actually no need o make such functions, much less check the stack. Also, either your traverseMaze function should take in a row and col argument for the starting position, or you should put such information inside your class as private variables.
简单地做类似的事情
//assuming that current spot is at r,c
if (mazePoints[r-1][c] == 'O'){ //up dir
pointsInMaze.push(new Point(r, c));
mazePoints[r-1,c] = ''; //empty char marks where you've already been
}
//other directions ommitted here
现在您要做的就是将上述内容放入提供的算法中的循环中，它应该可以工作.请注意，我在这里将将数组中的当前点标记为已访问"行更改为将邻居标记为已访问"，因为检查堆栈内是否存在一个点效率不高.在推送它们时将它们标记为已访问要容易得多进入堆栈.但是，您仍然需要在开始循环时将起始位置标记为已访问
Now all you have to do is put the above into the loop in the algorithm provided and it should work. Note that I changed the "mark current spot in the array as 'visited' line to "mark neighbors as visited" here because checking whether a point exists inside the stack is not efficient. Much easier to just mark them as visited as you push them into the stack. However, you still need to mark your starting position as visited when you begin your loop
这篇关于我的迷宫检查器怎么了???(爪哇)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！