java - 我无法显示迷宫内从开始到结束的路径

Question

我正在从输入文件中读取迷宫轮廓并将值存储在二维数组中。我能够在 findPath() 方法中找到导出，但我不确定如何从开始到结束跟踪实际路径。

我想将“Room”中的字符值更改为“.”如果它在实际路径上。请告诉我如何才能做到这一点。任何帮助是极大的赞赏。谢谢。

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.*;
import javax.swing.JOptionPane;

public class Maze {
    String inFile,   // Name of file to be used as input
           outFile,  // Name of file to output completed maze to
           line;     // Current line being read by scanner
    Room [][] rooms; // Holds the values that create maze
    Room [] theStack;
    Room goal;
    Room current = new Room();
    int rows, columns;
    int tos = 0;
    char [][] mazeC;

    public static void main(String []args) throws Exception {
        Maze m = new Maze();
    }

    public Maze() throws FileNotFoundException {
        // Prompts user for the name of the file they wish to use as the input file.
        inFile = JOptionPane.showInputDialog(null, "Please enter the name of the file you wish to read, including " + "the file path:");
        if(inFile.equals("")) inFile = "C:/java/javaFiles/maze1.txt";

        // Prompts user to enter the name they wish to save the file under.
        outFile = JOptionPane.showInputDialog(null, "Please enter the filename you wish to save the data to:");
        if(outFile.equals("")) outFile = "C:/java/javaFiles/mazeoutput1.txt";

        // Creates a scanner object to read in the input file.
        Scanner readFile = new Scanner(new FileReader(inFile));
        PrintWriter output = new PrintWriter(outFile);        
        rows = readFile.nextInt();
        columns = readFile.nextInt();
        readFile.nextLine();
        theStack = new Room[1000];
        rooms = new Room [rows][columns];
        for(int i = 0; i < rows; i++) {
            line = readFile.nextLine();
            for(int j = 0; j< line.length(); j++) {
                Room r = new Room();
                r.setValue(line.charAt(j));
                if(r.getValue() == '$')
                    r.setGoal(true);
                r.setBlocked(false);
                if (r.getValue() == '*') {
                    r.setBlocked(true);
                    r.setGoal(false);
                } else {
                    r.setGoal(false);
                    r.setBlocked(false);
                }
                r.setCord(i, j);
                rooms[i][j] = r;
                //mazeContent[i][j]  = line.charAt(j);    
            }
        }

        createRooms();

        findPath();
        for(int i = 0; i < rows ; i++) {
            for(int j = 0; j < columns ; j++) {
                System.out.print(rooms[i][j].getValue());
            }
            System.out.println();
        }
    }

    public void createRooms() {
        for(int i = 1; i < rows - 1; i++) {
            for(int j = 1; j < columns -1; j++) {
                rooms[i][j].setCord(i,j);
                rooms[i][j].setValue(rooms[i][j].getValue());
                rooms[i][j].setUp(rooms, i, j);
                rooms[i][j].setDown(rooms, i, j);
                rooms[i][j].setRight(rooms, i, j);
                rooms[i][j].setLeft(rooms, i, j);
                if(rooms[i][j].getValue() == '*')
                    rooms[i][j].setBlocked(true);
                else
                    rooms[i][j].setBlocked(false);

                //System.out.println(rooms[i][j].getValue());
            }
        }
    }

    public void findPath() {
        for(int i = 0; i < rows ; i++) {
            for(int j = 0; j < columns ; j++) {
                System.out.print(rooms[i][j].getValue());
            }
            System.out.println();
        }
        Room start = rooms[1][1];
        push(start);
        while(!isEmpty()) { 
            current = pop();
            System.out.println("The value stored in current is" + current.getValue()+ "");
            if (current == null) 
                System.out.println("current is null");
            else if(current.getValue() == '$') {
                System.out.println("Success"); 
                current.setValue('f');
                /*for (int i = 0; i < tos; i++) {
                }*/
            }
            //System.out.println("The value is " + current.getValue());
            else if(current.getBlocked() == false && current.getVisited() == false) {
                System.out.println("pushing currents neighbors left, right....etc" + 
                    "current is at" +  current.getCord());
                current.setVisited(true);
                //
                if(current.getRight() != null){
                    push(current.getRight()); System.out.println("Inside push 1" +current.getRight().getCord());}
                else System.out.println("Inside push right is null");
                if(current.getLeft() != null){
                    push(current.getLeft()); System.out.println("Inside push 2 " + current.getLeft().getCord());}
                else System.out.println("Inside push left is null");
                if(current.getUp() != null)  {
                    push(current.getUp()); System.out.println("Inside push 3" + current.getUp().getCord());}
                else System.out.println("Inside push up is null");
                if(current.getDown() != null) {
                    push(current.getDown()); System.out.println("inside push 4" + current.getDown().getCord());}
                else System.out.println("Inside push down is null");
            }
        }
    }

    public Room pop() {
        // TODO Auto-generated method stub
        System.out.println("I have Popped");
        return theStack[--tos];
    }

    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return tos == 0;
    }

    public void push(Room item) {
        System.out.println("I have pushed");
        if (isFull()) {
            System.out.println("The stack is full!");
        }
        else if(item == null){
            System.out.println("you are pushing a null object");
        }
        else 
            System.out.println("stuff added");
        theStack[tos++] = item;
    }

    public boolean isFull() {
        return tos == theStack.length-1;
    }
 }

Answer 1

我还没有真正逐行查看你的代码，但这里有一个解决方案:(我编写了一个类似的程序来查找图中的 Djikstra 最短路径)

在房间对象中创建一个名为PREVIOUS的属性。每次您前往“下一个房间”时，请确保将下一个房间的PREVIOUS属性更改为您来自的房间。

当您到达目的地时:从目的地的PREVIOUS开始，然后遍历各个房间，直到找到没有PREVIOUS的房间，这将是您的源(起始)房间。 即转到上一个房间，将其添加到堆栈中，转到上一个房间，然后重复该过程，直到到达起始房间。

这应该有效，因为:如果你穿过一条房间路径并且遇到了死胡同，你将原路返回并开始走一条新路径。最终，您将递归地覆盖新路径中每个房间的 PREVIOUS 属性(每次)。当您到达目的地时，您当前(正确)路径中的每个房间都将拥有最新(正确)的PREVIOUS属性。因此，回溯并将每个房间的PREVIOUS添加到堆栈或队列或(无论您想要什么)中。这应该给你你的路径。