创建Java中的迷宫求解算法 [英] Creating a maze solving algorithm in Java
问题描述
我被分配了建立在Java迷宫求解器的任务。这里的任务：
I've been assigned with the task of creating a maze solver in Java. Here's the assignment:
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'重presents墙壁或阻塞位置和字符'O'再presents的 打开位置。你可以假设入口的迷宫总是在右下 角，而出口总是在左上角。你的程序应该派 输出到文件。如果找到一个路径输出文件应该包含的路径。如果路径 未找到的消息应该发送到该文件。请注意，一个迷宫可以具有多于 一个解决方案的路径，但在这个练习中，您只被要求找到一个解决方案，而不是 所有的解决方案。
The character 'X' represents a wall or a blocked position and the character 'O' represents an open position. You may assume that the entrance to the maze is always in the lower right hand corner, and the exit is always in the upper left hand corner. Your program should send its output to a file. If a path is found the output file should contain the path. If a path is not found a message should be sent to the file. Please note that a maze may have more than one solution path, but in this exercise you are only being asked to locate one solution, not all solutions.
你的程序应该使用堆栈来记录它正在探索的路径和原路返回时， 到达阻塞位置。
Your program should use a stack to record the path that it is exploring and backtrack when it reaches a blocked position.
请务必写你的code之前写一个完整的算法。随意创建任何附加 课程将帮助您完成任务。
Be sure to write a complete algorithm before writing your code. Feel free to create any additional classes that will help you complete the assignment.
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
不管怎样，我已经建立了为已设定/一分类get方法在所有主要的方向，这将返回布尔旅游，如下所示：
Anyway, what I have set up is a Points class that has set/get methods for traveling in all cardinal directions which will return booleans as shown:
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;
}
}
我只是随便得到实际的解决下来的主要问题。这是我有：
I'm just having problems getting the actual solving down in the main. Here's what I have:
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++
}
除了任何语法错误，可能你们给我一些帮助？非常感谢。
Aside from any syntax errors, could you guys offer me some help? Thanks a lot.
推荐答案
我在这里提出了类似的回答迷宫用C求解算法++
I submitted a similar answer here Maze Solving Algorithm in C++.
要在解决这一个机会，你应该：
To have a chance in solving it, you ought to:
- 创建一个
解决（）常规和递归调用自身：- 如果第1，第2，第3，...是真实的
解决已成功地找到解决办法 - 如果第1，第2，第3，...包含一个错误，它必须走回头路，另谋出路
- Create a
Solve()routine and recursively call itself:- if 1st, 2nd, 3rd, ... are true
Solvehas succeeded in finding a solution - if 1st, 2nd, 3rd, ... contains a false, it has to backtrack and find another way
- 为你出招它需要密切关注它
- 当我们到了一个死胡同，我们需要擦除不好的举动
- 我们可以实现上面燃烧的猜测，并删除它，如果它是错的
下面是一些伪code的解决方案。
Here's some pseudo code for the solution.
boolean solve(int X, int Y) { if (mazeSolved(X, Y)) { return true; } // Test for (X + 1, Y) if (canMove(X + 1, Y)) { placeDude(X + 1, Y); if (solve(X + 1, Y)) return true; eraseDude(X + 1, Y); } // Repeat Test for (X - 1, Y), (X, Y - 1) and (X, Y + 1) // ... // Otherwise force a back track. return false; }这篇关于创建Java中的迷宫求解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
- if 1st, 2nd, 3rd, ... are true
- 如果第1，第2，第3，...是真实的
