迷宫求解算法（java版）

_Zhao 发布于2019-08-14 18:03 / 2321人阅读

摘要：更多关于的文章请戳这里您的留言意见是对我最大的支持我的文章列表

迷宫求解算法一直是算法学习的经典，实现自然也是多种多样，包括动态规划，递归等实现，这里我们使用穷举求解，加深对栈的理解和应用

定义Position类用于存储坐标点

起点坐标为（1，1），终点坐标为（8，8）
地图打印在最下面

class Position {
    private int px;
    private int py;
    public Position(int px, int py) {
        this.px = px;
        this.py = py;
    }
    public int getPx() {
        return px;
    }
    public void setPx(int px) {
        this.px = px;
    }
    public int getPy() {
        return py;
    }
    public void setPy(int py) {
        this.py = py;
    }
}

这里我们简单介绍下move()函数

move函数分别向四个方向移动，然后将可行的path入栈.
注意，这里栈元素中每个栈元素Position都是new出来的，栈中存的是reference，
注意看下面这种写法：

currentPosition.setPy(currentPosition.getPy()+1);
stacks.push(currentPosition);

这种写法一度让我陷入困惑，因为pop出来的Position都是一样的，原因大家可能应该明白了。。。

 public void move() {
        if (moveRight()) {
            Position temp = new Position(currentPosition.getPx() + 1, currentPosition.getPy());
            test.add(temp);
            stacks.push(temp);
        } else if (moveBottom()) {
            Position temp = new Position(currentPosition.getPx(), currentPosition.getPy() + 1);
            test.add(temp);
            stacks.push(temp);
        } else if (moveTop()) {
            Position temp = new Position(currentPosition.getPx(), currentPosition.getPy() - 1);
            test.add(temp);
            stacks.push(temp);
        } else if (moveLeft()) {
            Position temp = new Position(currentPosition.getPx() - 1, currentPosition.getPy());
            test.add(temp);
            stacks.push(temp);
        } else {
            currentPosition = stacks.pop();//若当前位置四个方向都走不通，则将当前位置出栈，继续遍历上一节点
        }
    }

整体代码

class Position {
    private int px;
    private int py;
    public Position(int px, int py) {
        this.px = px;
        this.py = py;
    }
    public int getPx() {
        return px;
    }
    public void setPx(int px) {
        this.px = px;
    }
    public int getPy() {
        return py;
    }
    public void setPy(int py) {
        this.py = py;
    }
}
public class Maze {
    private final Position start;//迷宫的起点final
    private final Position end;//迷宫的终点final
    private ArrayList footPrint;//足迹
    private ArrayList test;
    private MyStack stacks;//自定义栈（也可以用java.util中的Stack栈）若想了解MyStack的实现，可以参考我的另一篇博客
    private Position currentPosition;//定义当前位置
    public Maze() {//集合，栈的初始化工作
        start = new Position(1, 1);
        end = new Position(8, 8);
        currentPosition = start;
        stacks = new MyStack<>();
        test = new ArrayList<>();
    }
    public static final int map[][] = //定义地图10*10的方格
            {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
            {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
            {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
            {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
            {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
            {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
            {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    public static void printMap() {//打印地图
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (map[i][j] == 1) System.out.print(" ■");
                else System.out.print("  ");
            }
            System.out.println();
        }
    }
    public boolean moveTop() {//上移
        String s = currentPosition.getPx() + "" + (currentPosition.getPy() - 1);
        if ((map[currentPosition.getPx()][currentPosition.getPy() - 1] != 1) & !isArrived(s)) {
            footPrint.add(s);
            return true;
        }
        return false;
    }
    public boolean moveRight() {//右移
        String s = (currentPosition.getPx() + 1) + "" + currentPosition.getPy();
        if (map[currentPosition.getPx() + 1][currentPosition.getPy()] != 1 & !isArrived(s)) {
            footPrint.add(s);
            return true;
        }
        return false;
    }
    public boolean moveBottom() {//下移
        String s = currentPosition.getPx() + "" + (currentPosition.getPy() + 1);
        if ((map[currentPosition.getPx()][currentPosition.getPy() + 1] != 1) & !isArrived(s)) {
            footPrint.add(s);
            return true;
        }
        return false;
    }
    public boolean moveLeft() {//左移
        String s = (currentPosition.getPx() - 1) + "" + currentPosition.getPy();
        if ((map[currentPosition.getPx() - 1][currentPosition.getPy()] != 1) & !isArrived(s)) {
            footPrint.add(s);
            return true;
        }
        return false;
    }
    public boolean isArrived(String position) {//判断当前位置是否已经到打过
        return footPrint.contains(position);
    }
    public void move() {//move函数分别向四个方向移动，然后将可行的path入栈
        if (moveRight()) {
            Position temp = new Position(currentPosition.getPx() + 1, currentPosition.getPy());
            test.add(temp);
            stacks.push(temp);
        } else if (moveBottom()) {
            Position temp = new Position(currentPosition.getPx(), currentPosition.getPy() + 1);
            test.add(temp);
            stacks.push(temp);
        } else if (moveTop()) {
            Position temp = new Position(currentPosition.getPx(), currentPosition.getPy() - 1);
            test.add(temp);
            stacks.push(temp);
        } else if (moveLeft()) {
            Position temp = new Position(currentPosition.getPx() - 1, currentPosition.getPy());
            test.add(temp);
            stacks.push(temp);
        } else {
            currentPosition = stacks.pop();//若当前位置四个方向都走不通，则将当前位置出栈，继续遍历上一节点
        }
    }
    public static void main(String[] args) {
        Maze m = new Maze();
        m.footPrint = new ArrayList<>();
        m.footPrint.add("11");
        m.stacks.push(m.start);
        while (m.currentPosition.getPx() != 8 || m.currentPosition.getPy() != 8) {
            m.move();
        }
        printMap();
        System.out.println("下面是足迹,长度是：" + m.footPrint.size());
        m.printFootPrint();
    }
    public void printFootPrint() {
        for (int i = 0; i < footPrint.size(); i++) {
            System.out.print(footPrint.get(i) + ",");
        }
        System.out.println();
    }
}

大家可能会疑惑，为什么足迹是不连续的（例如：21，12）两个位置是走不通的，是因为在path遍历过程中存在跳栈，既当前位置走不通便会将当前位置的Position出栈（stacks.pop），然后继续上一节点遍历。

更多关于java的文章请戳这里:（您的留言意见是对我最大的支持）

我的文章列表

Email:sxh13208803520@gmail.com

GPU云服务器云服务器迷宫求解栈 c语言迷宫求解的程序c语言自然迷宫算法 python走迷宫算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66962.html

用并查集(find-union)实现迷宫算法以及最短路径求解

摘要：本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言迷宫对于大家都不会陌生那么迷宫是怎么生成已经迷宫要如何找到正确的路径呢用代码又怎么实现带着这些问题我们继续往下看并查集朋友圈有一种算法就做并查集什么意思呢比如现在有零本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

xiangchaobin 2019-08-16 10:30 评论0 收藏0
用队列求解迷宫最短路径及其应用(围住神经猫)

摘要：对应迷宫数组为实现语言实现求解方块类型方块行号方块列号上一个方块在队列中位置顺序队进队顺时针迷宫路径如下运行结果应用围住神经猫游戏使用写的项目源码下载体验最后附上我喜欢的歌的英文翻译心做问题给定一个M×N的迷宫图,求一条从指定入口到出口的最短路径.假设迷宫图如图所示(M=8, N=8) showImg(https://segmentfault.com/img/bVRjIk?w=26...

Achilles 2019-06-27 17:07 评论0 收藏0
递归实现迷宫求解

摘要：这周数据结构老师布置了一个作业，用栈来实现迷宫的求解，本来是要求自己写一个栈的类来实现，但是自己懒得写了，因为递归也是栈的一种实现，就直接用了递归来写。这周数据结构老师布置了一个作业，用栈来实现迷宫的求解，本来是要求自己写一个栈的类来实现，但是自己懒得写了，因为递归也是栈的一种实现，就直接用了递归来写。迷宫求解，主要用的是穷举法:从起始位置开始，向东南西北四个方向每个方向都尝试走，...

habren 2019-08-19 11:14 评论0 收藏0
算法（第4版） Chapter 4.1 无向图

摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

kamushin233 2019-08-14 17:14 评论0 收藏0
[ JavaScript ] 数据结构与算法 —— 栈

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。前言 JavaScript是当下最流行的编程语言之一，它可以做很多事情：数据可视化（D3.js，Three.js，Chart.js）; 移动端应用(React Native,Weex,AppCan,Fl...

everfight 2019-08-26 13:31 评论0 收藏0