Tôi đã được chỉ định với nhiệm vụ tạo trình giải quyết mê cung trong Java. Dưới đây là các bài tập:Tạo thuật toán giải quyết mê cung trong 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
Nhân vật 'X' đại diện cho một bức tường hoặc một vị trí bị chặn và các nhân vật 'O' đại diện cho một vị trí mở . Bạn có thể giả định rằng lối vào mê cung luôn ở góc dưới bên phải góc và lối ra luôn ở góc trên bên trái. Chương trình của bạn nên gửi đầu ra của nó vào một tệp. Nếu đường dẫn được tìm thấy, tệp đầu ra sẽ chứa đường dẫn. Nếu đường dẫn là , không tìm thấy thư nào được gửi đến tệp. Xin lưu ý rằng một mê cung có thể có nhiều hơn một đường dẫn giải pháp, nhưng trong bài tập này, bạn chỉ được yêu cầu xác định một giải pháp, không phải tất cả các giải pháp.
Chương trình của bạn nên sử dụng ngăn xếp để ghi lại đường dẫn mà nó đang khám phá và quay lại khi nó đạt đến vị trí bị chặn.
Hãy chắc chắn viết một thuật toán hoàn chỉnh trước khi viết mã của bạn. Vui lòng tạo thêm các lớp học bổ sung để giúp bạn hoàn tất bài tập.
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
Dù sao, những gì tôi đã thiết lập là một lớp điểm đã thiết lập/lấy phương pháp cho việc đi lại trong tất cả các hướng chính mà sẽ trả về boolean như:
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;
}
}
tôi chỉ là có vấn đề nhận được giải quyết thực tế trong chính. Dưới đây là những gì tôi có:
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++
}
Ngoài bất kỳ lỗi cú pháp nào, các bạn có thể cung cấp cho tôi một số trợ giúp không? Cảm ơn rất nhiều.
gì lỗi cụ thể là bạn gặp phải? – templatetypedef
Bạn có thể mô tả các vấn đề bạn đang gặp phải không? Bạn nghĩ điều này không chính xác theo cách nào? –
Tôi không chắc liệu tôi có đang kiểm tra chính xác hàng xóm thực sự hay không, như lặp lại qua mê cung – Copernikush