java - 在 Java 中创建迷宫求解算法

Question

我被分配了用 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”代表一个 开仓。你可能会假设迷宫的入口总是在右下角 角，导出总是在左上角。你的程序应该发送它的 输出到一个文件。如果找到路径，则输出文件应包含该路径。如果路径是 未找到消息应发送到文件。请注意，一个迷宫可能有超过 一个解决方案路径，但在本练习中只要求您找到一个解决方案，而不是 所有解决方案。

你的程序应该使用堆栈来记录它正在探索的路径，并在它返回时 到达阻塞位置。

请务必在编写代码之前编写完整的算法。随意创建任何额外的 帮助您完成作业的类(class)。

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 类，它具有在所有主要方向上行驶的设置/获取方法，它将返回 boolean 值，如下所示:

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++
}

除了任何语法错误，你们能给我一些帮助吗？非常感谢。

Answer 1

我在这里提交了一个类似的答案Maze Solving Algorithm in C++ .

要有机会解决它，您应该:

• 创建一个 Solve() 例程并递归调用自身:
  • if 1st, 2nd, 3rd, ... 为真 Solve 已成功找到解决方案
  • 如果 1st, 2nd, 3rd, ... 包含错误，它必须回溯并找到另一条路
• 你需要建立一个你去过的地方的缓冲区以避免无限循环
  • 当你移动时，它需要密切关注它
  • 当我们走到死胡同时，我们需要消除错误的举动
  • 我们可以通过刻录猜测并在错误时将其删除来实现上述内容

这是解决方案的一些伪代码。

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;
 }