俞唐
2021-06-13 10:33
采纳率: 50%
浏览 46

java实现迷宫问题

给定一个迷宫,阵列中每个元素用0或1表示。0表示可以走,1表示不可走。给定入口位置后,用程序找到出口。输出从入口到出口的路径,路径中每一个节点位置用二维数组(左上角为0,0)表示,并找出最短路径

以下面4*4的迷宫举例,入口为(0,1)

1011

1001

1100

1111

输出应该为:

(0,1)

(1,1)

(1,2)

(2,2)

(2,3)

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • CSDN专家-张老师 2021-06-13 10:35
    已采纳
    /**
     * @author cuiods
     */
    public class MazeCell {
        private int x;
        private int y;
        private int step;
     
        public MazeCell(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
     
        public int getX() {
            return x;
        }
     
        public void setX(int x) {
            this.x = x;
        }
     
        public int getY() {
            return y;
        }
     
        public void setY(int y) {
            this.y = y;
        }
     
        public int getStep() {
            return step;
        }
     
        public void setStep(int step) {
            this.step = step;
        }
    }
    
    import java.util.Scanner;
    import java.util.Stack;
     
    /**
     * 迷宫类
     * 找到所有到达终点的路径
     * @author cuiods
     */
    public class Maze {
     
        /**
         * 临时保存路径
         */
        private Stack<MazeCell> pathStack = new Stack<>();
        /**
         * 保存迷宫
         */
        private int[][] maze;
        private boolean flag = false;
        private MazeCell startCell;
        private MazeCell endCell;
     
        public Maze() {
            initialMaze();
        }
     
        /**
         * 寻找路径
         */
        public void findPath() {
            assert flag;
            processCell(startCell.getX(), startCell.getY(), startCell.getStep());
        }
     
        private void processCell(int x, int y, int step) {
            if (x == endCell.getX() && y == endCell.getY()) {
                pathStack.pop();
                printPath();
                System.out.println("("+endCell.getX()+","+endCell.getY()+")");
                return;
            }
            test(x,y-1,step+1);
            test(x,y+1,step+1);
            test(x-1,y,step+1);
            test(x+1,y,step+1);
        }
     
        private void test(int x, int y, int step) {
            if (canGo(x,y)){
                MazeCell mazeCell = new MazeCell(x,y,step);
                insertToPath(mazeCell);
                processCell(x,y,step);
            }
        }
     
        private void printPath(){
            for (int i = 0; i < pathStack.size(); i++) {
                MazeCell cell = pathStack.get(i);
                System.out.print("("+cell.getX()+","+cell.getY()+")->");
            }
        }
     
        private void insertToPath(MazeCell mazeCell) {
            while (pathStack.peek().getStep() >= mazeCell.getStep()) {
                pathStack.pop();
            }
            pathStack.push(mazeCell);
        }
     
        private boolean canGo(int x, int y) {
            if (maze[x][y]==1) {
                return false;
            }
            for (int i = 0; i < pathStack.size(); i++) {
                MazeCell mazeCell = pathStack.get(i);
                if (mazeCell.getX()==x && mazeCell.getY()==y) {
                    return false;
                }
            }
            return true;
        }
     
        private void initialMaze() {
            int column;
            int row;
            Scanner scanner = new Scanner(System.in);
            int temp = 0;
            do {
                System.out.println("请输入迷宫行数(>0):");
                temp = scanner.nextInt();
            } while (temp<=0);
            row = temp;
            do {
                System.out.println("请输入迷宫列数(>0):");
                temp = scanner.nextInt();
            } while (temp<=0);
            column = temp;
            maze = new int[row+2][column+2];
            System.out.println("请输入迷宫(1为墙,0为路,-1为起点,2为终点):");
            for (int i = 0; i < column+2; i++) {
                maze[0][i] = 1;
            }
            for (int i = 1; i < row+1; i++) {
                maze[i][0] = 1;
                for (int j = 1; j < column+1; j++) {
                    temp = scanner.nextInt();
                    switch (temp) {
                        case -1:
                            startCell = new MazeCell(i,j,0);
                            maze[i][j] = temp;
                            pathStack.push(startCell);
                            break;
                        case 2:endCell = new MazeCell(i,j,-1);
                        case 0:
                        case 1:maze[i][j] = temp;break;
                        default:
                            System.out.println("输入不符合要求T T");
                            return;
                    }
                }
                maze[i][column+1] = 1;
            }
            for (int i = 0; i < column+2; i++) {
                maze[row+1][i] = 1;
            }
            if (startCell!=null && endCell!=null) {
                flag = true;
                System.out.println("输入成功:)");
            } else {
                System.out.println("至少要有一个起点和终点:(");
            }
        }
    }
    
    /** 测试类
     * @author csdn-zhangteacher
     * test main
     */
    public class Main {
     
        public static void main(String[] args) {
            Maze maze = new Maze();
            maze.findPath();
        }
    }
    已采纳该答案
    2 打赏 评论
  • 有问必答小助手 2021-06-16 14:44

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps: 问答会员年卡【8折】购 ,限时加赠IT实体书,即可 享受50次 有问必答服务,了解详情>>>https://t.csdnimg.cn/RW5m

    打赏 评论

相关推荐 更多相似问题