java - 迷宫程序无法完成

Question

所以我正在编写一个生成然后解决迷宫的程序。除了这件小事，我一切正常。迷宫中的标记将到达完成迷宫的倒数第二步，然后停下来，然后向不同的方向移动。我已经为此工作了大约 2 个小时，跟踪我的代码，但似乎无法找到它在最后一步变得古怪的位置或原因。

迷宫的规则是 X 是墙，不能穿过，O 是可以穿过的可能区域， . 是起点。 - 是我已经移动到的路径。标记可以在任何序数或基本方向(北、东北等)上移动。

我有两个矩阵，一个叫做 mat，用 X 和 O 和 显示给用户- 的。我还有另一个名为 visited 的矩阵，它与 mat 大小相同，是一种幕后矩阵，它跟踪我可以或不能移动的坐标到。它为墙壁存储 W，为我已经访问过的坐标存储 Y，为我可以访问的坐标存储 N。

我解决迷宫的方法是检查从北开始的可能走法，然后绕着指南针逆时针方向移动，直到找到可能的走法。标记不能移动到它已经移动的位置。

如果我遇到一条有不止一个可能移动的分割路径，我会将该位置的坐标放在两个堆栈中，行称为 splitx ，列称为 splity 所以我可以稍后再回来。如果我遇到了一个死胡同，其中每个方 block 要么是一堵墙，要么已经被访问过，我会回溯到我的拆分路径堆栈中的最后一个坐标，关闭我刚刚移动到的路径，并弹出堆栈的顶部值。

我还有另一个名为 visitStack 的堆栈，它存储我所做的每一次移动，N 代表北方，NE 代表东北，等等。这让我可以回溯我的 Action 并转到我遇到的最后一条分割路径。这是代码，下面是一些选择的输出。如果您对代码或输出有任何疑问，或者只是一般性的澄清，请尽管提问。

import java.util.*;

public class MazeLab
{
    public static void main(String args[]) 
    {
        Scanner input = new Scanner(System.in);
        System.out.print("Enter random starting seed  ===>>  ");
        int seed = input.nextInt();

        Maze maze = new Maze(seed);
        maze.displayMaze();
        maze.solveMaze();
    }
}

class Maze
{

    private char mat[][];               // 2d character array that stores the maze display
    private char visited[][];           // 2d character array that works behind to scenes to let me know where I can or can't move
    private Stack<String> visitStack;           // stack that stores every move I make as N, NE, E, SE, etc
    private int nowR, nowC;                     // coordinates for current position in the matrix
    private int startRow, startCol;             // coordinates for the starting position
    private boolean done = false;               // not that important
    private Stack<Integer> splitx = new Stack<Integer>(); // row coord for split paths
    private Stack<Integer> splity = new Stack<Integer>(); // col coord for split paths
    Random random = new Random();

    public Maze(int seed)
    // constructor which generates the random maze, random starting location
    // and initializes Maze class values.  If the random value equals 0 the maze
    // store an 'X' otherwise it store an 'O' in the maze.
    {
        Random randomize = new Random(seed);
        mat = new char[12][12];
        visited = new char[12][12];
        for (int r = 0; r < 12; r++)
            for (int c = 0; c < 12; c++)
            {
                if (r == 0 || c == 0 || r == 11 || c == 11)
                    mat[r][c] = 'X';
                else
                {
                    int rndInt = randomize.nextInt(2);
                    if (rndInt == 0)
                        mat[r][c] = 'X';
                    else
                        mat[r][c] = 'O';
                }
            }
        mat[0][0] = 'O';
        startRow = randomize.nextInt(12);
        startCol = 11;
        nowR = startRow;
        nowC = startCol;
        mat[startRow][startCol] = '.';
        visitStack = new Stack<String>();

        for(int i = 0; i < mat.length; i++)
            for(int k = 0; k < mat[i].length; k++)
                if(mat[i][k] == 'X')
                    visited[i][k] = 'W';
                else
                    visited[i][k] = 'N';
//                                      Avoid going back to the starting point
        visited[nowR][nowC] = 'Y';
    }


    void displayMaze()
    // displays the current maze configuration
    {
        for (int r = 0; r < 12; r++)
        {
            for (int c = 0; c < 12; c++)
                System.out.print(mat[r][c] + "  ");
            System.out.println();
        }
        System.out.println();

        if(done == false)
            pause();
    }


    public void solveMaze()
    {
    // for testing purposes, this is not the real method
        for(int i = 0; i < 15; i++)
        {
            getMove();
            displayMaze();
        }
    }

    private int numMoves()
    // This method determines if a position has a valid move or not       
    {
        int moves = 0;
        if(nowR != 0 && visited[nowR-1][nowC] == 'N')
            moves++;
        if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N')
            moves++;
        if(nowC != 11 && visited[nowR][nowC+1] == 'N')
            moves++;
        if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N')
            moves++;
        if(nowR != 11 && visited[nowR+1][nowC] == 'N')
            moves++;
        if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N')
            moves++;
        if(nowC != 0 && visited[nowR][nowC-1] == 'N')
            moves++;
        if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N')
            moves++;
        return moves;
    }

    private void getMove()
    {
        if(numMoves() > 1)
        {
//                                      checks for split paths
//                                      north
            if(nowR != 0 && visited[nowR-1][nowC] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      northwest
            if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      west
            if(nowC != 0 && visited[nowR][nowC-1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      southwest
            if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      south
            if(nowR != 11 && visited[nowR+1][nowC] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      southeast
            if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      east
            if(nowC != 11 && visited[nowR][nowC+1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
//                                      northeast
            if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N')
            {
                splitx.push(nowR);
                splity.push(nowC);
            }
        }
        if(numMoves() > 0)
        {
//                                      moves the marker, oriented to the right
//                                      north
            if(nowR != 0 && visited[nowR-1][nowC] == 'N')
            {
                nowR--;
                visited[nowR][nowC] = 'Y';
                visitStack.push("N");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON NORTH");
            }
//                                      northwest
            else if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N')
            {
                nowR--;
                nowC--;
                visited[nowR][nowC] = 'Y';
                visitStack.push("NW");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON NORTHWEST");
            }   
//                                      west
            else if(nowC != 0 && visited[nowR][nowC-1] == 'N')
            {
                nowC--;
                visited[nowR][nowC] = 'Y';
                visitStack.push("W");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON WEST");
            }
//                                      southwest
            else if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N')
            {
                nowR++;
                nowC--;
                visited[nowR][nowC] = 'Y';
                visitStack.push("SW");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON SOUTHWEST");
            }
//                                      south
            else if(nowR != 11 && visited[nowR+1][nowC] == 'N')
            {
                nowR++;
                visited[nowR][nowC] = 'Y';
                visitStack.push("S");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON SOUTH");
            }
//                                      southeast
            else if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N')
            {
                nowR++;
                nowC++;
                visited[nowR][nowC] = 'Y';
                visitStack.push("SE");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON SOUTHEAST");
            }
//                                      east
            else if(nowC != 11 && visited[nowR][nowC+1] == 'N')
            {
                nowC++;
                visited[nowR][nowC] = 'Y';
                visitStack.push("E");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON EAST");
            }
//                                      northeast
            else if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N')
            {
                nowR--;
                nowC++;
                visited[nowR][nowC] = 'Y';
                visitStack.push("NE");
                mat[nowR][nowC] = '-';
//              System.out.println("PUSHING ON NORTHEAST");
            }
        }
        if(numMoves() == 0)
        {
            while(nowR != splitx.peek() && nowC != splity.peek())
            {
                switch(visitStack.pop())
                {
//                                  have to backtrack the opposite direction i previously went
                    case "N":   visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR++;
                                break;
                    case "NE":  visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR++;
                                nowC--;
                                break;
                    case "E":   visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowC--;
                                break;
                    case "SE":  visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR--;
                                nowC--;
                                break;
                    case "S":   visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR--;
                                break;
                    case "SW":  visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR--;
                                nowC++;
                                break;
                    case "W":   visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowC++;
                                break;
                    case "NW":  visited[nowR][nowC] = 'N';
                                mat[nowR][nowC] = 'O';
                                nowR++;
                                nowC++;
                                break;
                    default: System.out.println("SOMETHING WENT WRONG WITH BACKTRACKING");
                }
            }
//                                      blocks off dead ends
//                                      north
            if(nowR != 0 && visited[nowR-1][nowC] == 'N')
                visited[nowR-1][nowC] = 'Y';
//                                      northwest
            else if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N')
                visited[nowR-1][nowC-1] = 'Y';  
//                                      west
            else if(nowC != 0 && visited[nowR][nowC-1] == 'N')
                visited[nowR][nowC-1] = 'Y';
//                                      southwest
            else if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N')
                visited[nowR+1][nowC-1] = 'Y';
//                                      south
            else if(nowR != 11 && visited[nowR+1][nowC] == 'N')
                visited[nowR+1][nowC] = 'Y';
//                                      southeast
            else if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N')
                visited[nowR+1][nowC+1] = 'Y';
//                                      east
            else if(nowC != 11 && visited[nowR][nowC+1] == 'N')
                visited[nowR][nowC+1] = 'Y';
//                                      northeast
            else if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N')
                visited[nowR-1][nowC+1] = 'Y';

            splitx.pop();
            splity.pop();
        }
    }

    private void pause() 
    {   
        Scanner input = new Scanner(System.in); 
        String dummy;
        System.out.print("\nPress <Enter> to continue  ===>>  ");                       
        dummy = input.nextLine();                               
    }
}

这是标记穿过之前的迷宫。

这是尽头的迷宫。请注意，当标记应该向西北方向移动以完成迷宫时，它会在下一个回合停留在同一位置，然后在那个回合之后向南移动。

Answer 1

所以，您在位置 (1,1) 并找到两个走法:NW 和 S。

if(numMoves() > 1) 触发并将两者 压入堆栈。

if(numMoves() > 0) 触发并应用 NW 移动，将您留在 (0,0)。

if(numMoves() == 0) 触发并开始回溯，因为 (0,0) 没有移动。

2 个问题:

• 检测到您找到导出的代码在哪里？
• if(numMoves() == 0) 正在使用 新 坐标调用 numMoves()。将其更改为 else。