迷宮求解算法（java版）

_Zhao 發(fā)布于2019-08-14 18:03 / 2396人閱讀

摘要：更多關于的文章請戳這里您的留言意見是對我最大的支持我的文章列表

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

定義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()函數(shù)

move函數(shù)分別向四個方向移動，然后將可行的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();//若當前位置四個方向都走不通，則將當前位置出棧，繼續(xù)遍歷上一節(jié)點
        }
    }

整體代碼

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的實現(xiàn)，可以參考我的另一篇博客
    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) {//判斷當前位置是否已經(jīng)到打過
        return footPrint.contains(position);
    }
    public void move() {//move函數(shù)分別向四個方向移動，然后將可行的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();//若當前位置四個方向都走不通，則將當前位置出棧，繼續(xù)遍歷上一節(jié)點
        }
    }
    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();
    }
}

大家可能會疑惑，為什么足跡是不連續(xù)的（例如：21，12）兩個位置是走不通的，是因為在path遍歷過程中存在跳棧，既當前位置走不通便會將當前位置的Position出棧（stacks.pop），然后繼續(xù)上一節(jié)點遍歷。

更多關于java的文章請戳這里:（您的留言意見是對我最大的支持）

我的文章列表

Email:sxh13208803520@gmail.com

云服務器 GPU云服務器迷宮求解棧 c語言迷宮求解的程序c語言自然迷宮算法 python走迷宮算法

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.hztianpu.com/yun/66962.html

用并查集(find-union)實現(xiàn)迷宮算法以及最短路徑求解

摘要：本人郵箱歡迎轉載轉載請注明網(wǎng)址代碼已經(jīng)全部托管有需要的同學自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經(jīng)迷宮要如何找到正確的路徑呢用代碼又怎么實現(xiàn)帶著這些問題我們繼續(xù)往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現(xiàn)在有零本人郵箱: 歡迎轉載,轉載請注明網(wǎng)址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

xiangchaobin 2019-08-16 10:30 評論0 收藏0
用隊列求解迷宮最短路徑及其應用(圍住神經(jīng)貓)

摘要：對應迷宮數(shù)組為實現(xiàn)語言實現(xiàn)求解方塊類型方塊行號方塊列號上一個方塊在隊列中位置順序隊進隊順時針迷宮路徑如下運行結果應用圍住神經(jīng)貓游戲使用寫的項目源碼下載體驗最后附上我喜歡的歌的英文翻譯心做問題給定一個M×N的迷宮圖,求一條從指定入口到出口的最短路徑.假設迷宮圖如圖所示(M=8, N=8) showImg(https://segmentfault.com/img/bVRjIk?w=26...

Achilles 2019-06-27 17:07 評論0 收藏0
遞歸實現(xiàn)迷宮求解

摘要：這周數(shù)據(jù)結構老師布置了一個作業(yè)，用棧來實現(xiàn)迷宮的求解，本來是要求自己寫一個棧的類來實現(xiàn)，但是自己懶得寫了，因為遞歸也是棧的一種實現(xiàn)，就直接用了遞歸來寫。這周數(shù)據(jù)結構老師布置了一個作業(yè)，用棧來實現(xiàn)迷宮的求解，本來是要求自己寫一個棧的類來實現(xiàn)，但是自己懶得寫了，因為遞歸也是棧的一種實現(xiàn)，就直接用了遞歸來寫。迷宮求解，主要用的是窮舉法:從起始位置開始，向東南西北四個方向每個方向都嘗試走，...

habren 2019-08-19 11:14 評論0 收藏0
算法（第4版） Chapter 4.1 無向圖

摘要：邊僅由兩個頂點連接，并且沒有方向的圖稱為無向圖。用分隔符當前為空格，也可以是分號等分隔。深度優(yōu)先算法最簡搜索起點構造函數(shù)找到與起點連通的其他頂點。路徑構造函數(shù)接收一個頂點，計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

kamushin233 2019-08-14 17:14 評論0 收藏0
[ JavaScript ] 數(shù)據(jù)結構與算法 —— 棧

摘要：而且目前大部分編程語言的高級應用都會用到數(shù)據(jù)結構與算法以及設計模式。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。前言 JavaScript是當下最流行的編程語言之一，它可以做很多事情：數(shù)據(jù)可視化（D3.js，Three.js，Chart.js）; 移動端應用(React Native,Weex,AppCan,Fl...

everfight 2019-08-26 13:31 評論0 收藏0