如何在java中找到迷宫的其他解决方案？

kzmpq1sx  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(309)

我需要写一个程序，在给定的txt文件迷宫和打印解决方案的路径控制台。我写了这个程序，你可以看到下面，但我只能找到一个解决方案。如果迷宫里有不止一个解，我需要找到所有这些。我不知道我应该采取什么方法来解决这个问题。你能给个主意吗？
这是我的作品：
maze.txt（作为参数发送）

11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111

驾驶员等级：

import java.io.*;
import java.util.Arrays;

public class Driver {
    public static void main(String[] args) {

        //Reading source file
        int rowNum = 0, colNum = 0;
        File mazeFile = new File(args[0]);

        try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
            System.out.println("Input of Readed File:\n");
            String line;
            while ((line = br.readLine()) != null) {
                colNum = line.length();
                rowNum++;
                System.out.println(line);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        //creating new maze array
        char[][] maze = new char[rowNum][colNum];
        System.out.println();
        System.out.print("ROW: "+rowNum+" COL: "+colNum);

        //Setting maze's elements
        try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
            int readed,rNum=0,cNum=0;
            while ((readed = br.read()) != -1) {
                if(readed == 10){

                }
                else if(rNum<rowNum && cNum < colNum){
                    maze[rNum][cNum] = (char)readed;
                    cNum++;
                }
                else if(cNum >= colNum){
                    rNum++;
                    cNum=0;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        //Printing created maze...
        System.out.println("\nCreated Maze: \n");

        for (int i = 0; i<rowNum ; i++) {
            for (int j = 0; j < colNum; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }

        System.out.println("\nSolution: \n");
        //Creating myStack object for making stack operations
        Stack myStack = new Stack(1000);

        //Creating mazeSolver object for solving maze
        MazeSolver mazeSolver = new MazeSolver(myStack,maze,1,1,colNum-2,rowNum-2,rowNum,colNum);
        mazeSolver.solve();

        //Printing inside of our stack.
        //myStack.showElements();

        //Creating answer array
        char[][] answer = maze;

        //Our path is drawn by re-reading the stored data in our stack structure.
        for (int i = rowNum-1; i >=0; i--) {
            for (int j = colNum-1; j >=0; j--) {
                int x[] = myStack.peek();
                if(i == x[0] && j == x[1]){
                    answer[i][j] = '#';
                }
            }
        }

        //Minor visual improvements ...
        for (int i = 0; i<rowNum ; i++) {
            for (int j = 0; j < colNum; j++) {
                if(answer[i][j] == '1' || answer[i][j] == '0')
                    answer[i][j] = '.';
            }
        }

        //Printing our answer
        for (int i = 0; i<rowNum ; i++) {
            for (int j = 0; j < colNum; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }
}

堆栈类：

public class Stack {
    int topOfStack;
    int capacity;
    int[][] Stack;

    public Stack(int capacity) {
        this.capacity = capacity;
        Stack = new int[capacity][2];
        topOfStack = -1;
    }

    void push(int y, int x)
    {
        if(topOfStack == capacity){
            System.out.println("Stack Overflow...");
        }
        else{
            Stack[++topOfStack] = new int[] { y, x };
        }
        //System.out.println("###Pushed Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
    }

    int[] pop() {
        if (topOfStack < 0) {
            System.out.println("Stack is empty...");
            return null;
        }
        //System.out.println("Pulled Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
        topOfStack--;
        return Stack[topOfStack];
    }

    int[] pop2() {
        if (topOfStack < 0) {
            System.out.println("Stack Underflow");
            return null;
        }
        else {
            int x[] = Stack[topOfStack--];
            //System.out.println("Pulled Element: "+x[0]+" "+x[1]);
            return x;
        }
    }

    int[] peek()
    {
        if (topOfStack < 0) {
            System.out.println("Stack Underflow");
            return null;
        }
        else {
            int x[] = Stack[topOfStack];
            return x;
        }
    }

    void showElements()
    {
        System.out.println("\n\n");
        for (int i = topOfStack; i >=0; i--) {
            System.out.println("Stack Elements "+i+":"+" "+Stack[i][0] +" "+Stack[i][1]);
        }
    }

    int size(){
        int i;
        for (i = 0; i <= topOfStack; i++) {
        }
        return i;
    }
}

mazesolver等级：

public class MazeSolver {
    Stack workStack;
    char[][] maze;
    int startPointX;
    int startPointY;
    int endPointX;
    int endPointY;
    int numberOfRows;
    int numberOfCols;
    static final char Wall = '1';
    static final char Free = '0';
    static final char Success = '#';

    public MazeSolver(Stack workStack, char[][] maze,int startingPointX, int startingPointY, int endPointX, int endPointY, int RowNum, int ColNum) {
        this.workStack = workStack;
        this.maze = maze;
        this.startPointX = startingPointX;
        this.startPointY = startingPointY;
        this.endPointX = endPointX;
        this.endPointY = endPointY;
        this.numberOfRows = RowNum;
        this.numberOfCols = ColNum;
        workStack.push(startPointY,startingPointX);
    }

    boolean canMoveEast(){
        if((maze[startPointY][startPointX + 1] == Free) && (startPointX + 1 <= numberOfCols))
        {
            return true;
        }
        else
            return false;
    }

    boolean canMoveWest(){
        if((maze[startPointY][startPointX - 1] == Free) && (startPointX - 1 <= numberOfCols)){
            return true;
        }
        else
            return false;
    }

    boolean canMoveNorth(){
        if((maze[startPointY-1][startPointX] == Free) && (startPointY - 1 <= numberOfRows)){
            return true;
        }
        else
            return false;
    }

    boolean canMoveSouth(){
        if((maze[startPointY+1][startPointX] == Free) && (startPointY + 1 <= numberOfRows)){
            return true;
        }
        else
            return false;
    }

    boolean canMoveNorthEast(){
        if((maze[startPointY-1][startPointX+1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
            return true;
        }
        else
            return false;
    }

    boolean canMoveNorthWest(){
        if((maze[startPointY-1][startPointX-1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
            return true;
        }
        else
            return false;
    }
    boolean canMoveSouthEast(){
        if((maze[startPointY+1][startPointX+1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
            return true;
        }
        else
            return false;
    }
    boolean canMoveSouthWest(){
        if((maze[startPointY+1][startPointX-1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
            return true;
        }
        else
            return false;
    }

    boolean solve()
    {
        maze[startPointY][startPointX] = Success;

        //Checked if we reached our goal
        if((startPointY == endPointY) && (startPointX == endPointX)){
            return true;
        }

        if(canMoveEast()){
            workStack.push(startPointY,startPointX+1);
            startPointX++;
            solve();
        }
        else if(canMoveWest()){
            workStack.push(startPointY,startPointX-1);
            startPointX--;
            solve();
        }
        else if(canMoveNorth()){
            workStack.push(startPointY-1,startPointX);
            startPointY--;
            solve();
        }
        else if(canMoveSouth()){
            workStack.push(startPointY+1,startPointX);
            startPointY++;
            solve();
        }
        else if(canMoveNorthEast()){
            workStack.push(startPointY-1,startPointX+1);
            startPointY--;
            startPointX++;
            solve();
        }
        else if(canMoveNorthWest()){
            workStack.push(startPointY-1,startPointX-1);
            startPointY--;
            startPointX--;
            solve();
        }
        else if(canMoveSouthEast()){
            workStack.push(startPointY+1,startPointX+1);
            startPointY++;
            startPointX++;
            solve();
        }
        else if(canMoveSouthWest()){
            workStack.push(startPointY+1,startPointX-1);
            startPointY++;
            startPointX--;
            solve();
        }
        else if(true){
            try {
                maze[startPointY][startPointX] = Wall;
                int[] back = workStack.pop();
                startPointY = back[0];
                startPointX = back[1];
                solve();
            } catch (Exception e) {
                System.out.println("There is no solution!");
                System.exit(0);
            }
        }

        return false;
    }
}

我得到的输出：

Input of Readed File:

11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111

ROW: 13 COL: 17
Created Maze: 

11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111

Solution: 

.................
.#...............
..##...#.........
....###.#........
........#........
........#........
........#........
.......#.........
........#........
........#..####..
.........##....#.
...............#.
.................

Process finished with exit code 0

我需要的输出：

Input of Readed File:

11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111

ROW: 13 COL: 17
Created Maze: 

11111111111111111
10110011000111111
11001110111001111
10110001011100111
11101111011011001
11101001011011111
11011011011001011
10111100111110111
11011011011111101
11100111011000011
10011110100111101
10100110111111101
11111111111111111

Solution 1: 

.................
.#...............
..##...#.........
....###.#........
........#........
........#........
........#........
.......#.........
........#........
........#..####..
.........##....#.
...............#.
.................

Solution 2:

.................
.#...............
..##.............
....#............
...#.............
...#.............
..#..............
.#....##.........
..#..#..#........
...##...#..####..
.........##....#.
...............#.
.................

Process finished with exit code 0
JavaArraysstackoop

1条答案

按热度按时间
cedebl8k

cedebl8k1#

你想要的结果是'各种各样的解决方案，可以通过（东北，西北）到（东南，西南）'，你需要解决使用堆栈？如果是这样的话，我建议您使用两个堆栈，一个用于保存所有的可能性（将所有的toeast、totest等存储在您可以去的地方），另一个用于保存当前的ongoings（每个可能的解决方案，作为缓冲区）
只需添加将当前进程保存在缓冲区中的逻辑，并在它是原始代码上的解决方案时打印路径。如果它不是一个解决方案，并且无法到达（东南、西南），则回溯并恢复缓冲区堆栈。对于这个逻辑，您需要另一个保存堆栈的位置，您最后从不同的方向选择的位置。
总之，

Stack1 => to save all possibilities
Stack2 => current paths. If not a solution, delete and restore
Stack3 => where you chose one direction from many. Need to traceback the path.

Stack2 copies Stack1 whenever you progress,
when reach the goal you print your Stack2 as a solution,
if not, pop until your latest decision informed by popping Stack3.
赞(0）分享  回复(0）举报  2021-07-06
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com