我被分配了一个任务,需要使用Java编写一个迷宫求解器。以下是任务要求:
Write an application that finds a path through a maze.
The maze should be read from a file. A sample maze is shown below.
O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O
X X O X X X O
字符'X'代表墙或者阻塞位置,字符'O'代表开放位置。假设迷宫的入口总是在右下角,出口总是在左上角。你的程序应该将输出写入文件。如果找到了一条路径,则输出文件应包含该路径。如果没有找到路径,则应向文件发送消息。请注意,一个迷宫可能有多条解决方案的路径,但在这个练习中,您只需要找到一条解决方案,而不是所有的解决方案。
您的程序应该使用堆栈来记录正在探索的路径,并在到达阻塞位置时回溯。
在编写代码之前,请确保编写完整的算法。可以自由创建任何其他类来帮助完成任务。
Here's my Algorithm:
1)Initialize array list to hold maze
2)Read text file holding maze in format
o x x x x o
o o x o x x
o o o o o x
x x x x o o
3)Create variables to hold numbers of columns and rows
3)While text file has next line
A. Read next line
B. Tokenize line
C. Create a temporary ArrayList
D. While there are tokens
i. Get token
ii. create a Point
iii. add point to temp ArrayList
iv. increment maximum number of columns
E. Add temp to maze arraylist, increment max rows
F. initialize a hold of points as max rows - 1
G. Create a start point with x values as maximum number of rows - 1, and y values as maximum number of columns - 1
H. Create stack of points and push starting location
I. While finished searching is not done
i. Look at top of stack and check for finish
ii. check neighbors
iii. is there an open neighbor?
- if yes, update flags and push
- if no, pop from stack
J. Print solution
4. Done is true
无论如何,我设置了一个Points类,其中包含前进、后退、向左和向右移动的set/get方法,这些方法将返回布尔值,如下所示:
public class Points<E>
{
private int xCoord;
private int yCoord;
private char val;
private boolean N;
private boolean S;
private boolean E;
private boolean W;
public Points()
{
xCoord =0;
yCoord =0;
val =' ';
N = true;
S = true;
E = true;
W = true;
}
public Points (int X, int Y)
{
xCoord = X;
yCoord = Y;
}
public void setX(int x)
{
xCoord = x;
}
public void setY(int y)
{
yCoordinate = y;
}
public void setNorth(boolean n)
{
N = n;
}
public void setSouth(boolean s)
{
S= s;
}
public void setEast(boolean e)
{
E = e;
}
public void setWest(boolean w)
{
W = w;
}
public int getX()
{
return xCoord;
}
public int getY()
{
return yCoord;
}
public char getVal()
{
return val;
}
public boolean getNorth()
{
return N;
}
public boolean getSouth()
{
return S;
}
public boolean getEast()
{
return E;
}
public boolean getWest()
{
return W;
}
public String toString1()
{
String result = "(" + xCoord + ", " +yCoord + ")";
return result;
}
我在主程序中遇到了实际求解的问题。这是我的代码:
import java.io.*;
import java.util.*;
import java.lang.*;
import java.text.*;
public class MazeSolve1
{
public static void main(String[] args)
{
//Create arrayList of Points
ArrayList<ArrayList<Points>> MAZE = new ArrayList<ArrayList<Points>>();
Scanner in = new Scanner(System.in);
//Read File in
System.out.print("Enter the file name: ");
String fileName = in.nextLine();
fileName = fileName.trim();
FileReader reader = new FileReader(fileName+".txt");
Scanner in2 = new Scanner(reader);
//Write file out
FileWriter writer = new FileWriter("Numbers.out");
PrintWriter out = new PrintWriter(writer);
boolean done = false;
int maxCol = 0;
int maxRow = 0;
while(!done) {
//creating array lists
while (in2.hasNextLine()) {
//Read next line
String nextLine = in2.nextLine();
//Tokenize Line
StringTokenizer st = new StringTokenizer(nextLine, " ");
//Create temp ArrayList
ArrayList<ArrayList<Points>> temp = new ArrayList<ArrayList<Points>>();
//While there are more tokens
while (st.hasNextToken()) {
String token = st.nextToken();
Points pt = new Points();
temp.add(pt);
maxCol++
}
MAZE.add(temp);
maxRow++;
}
//create hold arraylist for max rows of maze -1
//create variables for start x and y coordinates
ArrayList<ArrayList<Points>> hold = new ArrayList<ArrayList<Points>>();
hold = MAZE.get(maxRow - 1);
int startColumn = hold.get(maxCol - 1);
int startRow = hold.get(maxRow - 1);
Point start = new Point();
start.setX(startColumn);
start.setY(startRow);
//initialize stack, and push the start position
MyStack<Points> st = new ArrayStack<Points>();
st.push(start.toString1());
//south and east of start are edges of array
start.setSouth(false);
start.setEast(false);
//while your position is not equal to point (0,0) [finish]
while (st.peek() != "(0, 0)") {
//getting the next coordinate to the North
int nextY = start.getY() - 1;
int nextX = start.getX();
//if character to the North is an O it's open and the North flag is true
if (hold.get(nextY) = 'O' && start.getNorth() == true) {
//set flags and push coordinate
start.setNorth(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop(); }
//look at coordinate to the East
nextX = start.getX() + 1;
//if character to the East is a O and the East flag is true
if (hold.get(nextX) = 'O' && start.getEast() == true) {
//set flags and push coordinate
start.setEast(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop(); }
//look at coordinate to the South
nextY = start.getY() + 1;
//if character to the South is a O and the West flag is true
if (hold.get(nextY) = 'O' && start.getSouth() == true) {
//set flags and push coordinate
start.setSouth(false);
st.push(start.toString1());
}
//else pop from stack
else { st.pop() }
//keep looping until the top of the stack reads (0, 0)
}
done = true;
}
//Print the results
System.out.println("---Path taken---");
for (int i = 0; i< st.size(); i++) {
System.out.println(st.pop);
i++
}
除了语法错误外,你们能给我提供一些帮助吗?非常感谢。