首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >迷宫程序无法完成

问迷宫程序无法完成
EN

Stack Overflow用户
提问于 2015-09-27 03:08:37
回答 1查看 330关注 0票数 2

所以我正在编写一个程序,生成并解决一个迷宫。除了这件小事我什么都能用。迷宫中的标记将到达完成迷宫的第二步到最后一步,然后停下来,然后移动到另一个方向。我已经做了大约两个小时的工作,跟踪我的代码,似乎找不到它在哪里或为什么在最后一步古怪。

迷宫的规则是:X是墙,不能移动,O是可以移动的可能区域,.是起点。-是我已经移动到的路径。该标记可以向任意的序号或基数方向移动(北、东北等)。

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

我解决迷宫的方法是检查从北开始的可能的移动,并在指南针逆时针方向移动,直到我找到可能的移动。标记无法移动到已移动的位置。

如果我遇到一个具有多个可能移动的分裂路径,我会将该位置的坐标放置在两个堆栈中,分别称为splitx表示行和splity表示列,以便稍后再回到它。如果我碰到一个死胡同,每个正方形要么是墙,要么已经被访问过,我将返回到拆分路径堆栈中的最后坐标,关闭我刚移动到的路径,并弹出堆栈的顶部值。

我还有另一个名为visitStack的堆栈,它存储了我为北方所做的每一次移动,以及东北地区的NE。这使我可以追溯我的移动,并进入我遇到的最后一条分割路径。下面是代码,下面是一些选定的输出。如果你对代码或输出有任何疑问,或者只是简单的澄清,那就去问吧。

代码语言:javascript
复制
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();                               
    }
}

这是在标记移动之前的迷宫。

​

这是最后的迷宫。注意,当标记向西北移动以完成迷宫时,它将在下一个拐弯处停留在相同的位置,然后再向南移动。

​

​

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-09-27 03:26:27

因此,您在位置(1,1),并发现两个移动: NW和S。

if(numMoves() > 1)在堆栈上激发和推送这两种情况。

if(numMoves() > 0)触发并应用NW移动,使您处于(0,0)。

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

2期:

  • 检测到你找到出口的代码在哪里?
  • if(numMoves() == 0)正在使用新的坐标调用numMoves()。将其更改为else。
票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/32804179

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档