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

定义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入栈.

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