摘要：更多關(guān)于的文章請(qǐng)戳這里您的留言意見是對(duì)我最大的支持我的文章列表

迷宮求解算法一直是算法學(xué)習(xí)的經(jīng)典，實(shí)現(xiàn)自然也是多種多樣，包括動(dòng)態(tài)規(guī)劃，遞歸等實(shí)現(xiàn)，這里我們使用窮舉求解，加深對(duì)棧的理解和應(yīng)用

起點(diǎn)坐標(biāo)為（1，1），終點(diǎn)坐標(biāo)為（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函數(shù)分別向四個(gè)方向移動(dòng)，然后將可行的path入棧.
注意，這里棧元素中每個(gè)棧元素Position都是new出來的，棧中存的是reference，
注意看下面這種寫法：

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

這種寫法一度讓我陷入困惑，因?yàn)閜op出來的Position都是一樣的，原因大家可能應(yīng)該明白了。。。

 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();//若當(dāng)前位置四個(gè)方向都走不通，則將當(dāng)前位置出棧，繼續(xù)遍歷上一節(jié)點(diǎn)
        }
    }

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;//迷宮的起點(diǎn)final
    private final Position end;//迷宮的終點(diǎn)final
    private ArrayList footPrint;//足跡
    private ArrayList test;
    private MyStack stacks;//自定義棧（也可以用java.util中的Stack棧）若想了解MyStack的實(shí)現(xiàn)，可以參考我的另一篇博客
    private Position currentPosition;//定義當(dāng)前位置
    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) {//判斷當(dāng)前位置是否已經(jīng)到打過
        return footPrint.contains(position);
    }
    public void move() {//move函數(shù)分別向四個(gè)方向移動(dòng)，然后將可行的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();//若當(dāng)前位置四個(gè)方向都走不通，則將當(dāng)前位置出棧，繼續(xù)遍歷上一節(jié)點(diǎn)
        }
    }
    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("下面是足跡,長(zhǎng)度是：" + 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();
    }
}

大家可能會(huì)疑惑，為什么足跡是不連續(xù)的（例如：21，12）兩個(gè)位置是走不通的，是因?yàn)樵趐ath遍歷過程中存在跳棧，既當(dāng)前位置走不通便會(huì)將當(dāng)前位置的Position出棧（stacks.pop），然后繼續(xù)上一節(jié)點(diǎn)遍歷。

更多關(guān)于java的文章請(qǐng)戳這里:（您的留言意見是對(duì)我最大的支持）

我的文章列表

Email:sxh13208803520@gmail.com