摘要:這周數據結構老師布置了一個作業,用棧來實現迷宮的求解,本來是要求自己寫一個棧的類來實現,但是自己懶得寫了,因為遞歸也是棧的一種實現,就直接用了遞歸來寫。
這周數據結構老師布置了一個作業,用棧來實現迷宮的求解,本來是要求自己寫一個棧的類來實現,但是自己懶得寫了,因為遞歸也是棧的一種實現,就直接用了遞歸來寫。
迷宮求解,主要用的是窮舉法:從起始位置開始,向東南西北四個方向每個方向都嘗試走,在每一個嘗試中,若可通,則納入當前路徑,將下一位置切換為當前位置,再開始進行嘗試,直到到達出口。若不可通,應回退到前一個通快,除去嘗試過的方向再探索,四個方塊都不可通,則刪除當前的通道塊,這個后進先出的操作,可以用棧來實現,當然也能用遞歸實現。
我想的是,迷宮應該有四個方法:
1.隨機初始化迷宮(設置起點,終點,障礙)
2.迷宮求解(算出迷宮的解答方法)
3.展示迷宮
4.判斷迷宮元素是否能夠移動
</>復制代碼
public interface Maze {
ArrayList> init(ArrayList> maze, int size, int obstacleNumber);//初始化迷宮
void show();//展示迷宮
boolean getAnswer(E element);//獲得迷宮的解
E move(int x, int y);//移動迷宮元素
}
在給迷宮初始化的時候遇到了問題,不能夠設置相同的起點和終點,不能設置相同的障礙,不能給起點和終點設置障礙。對于起點和終點,判斷一下就可以了,但是對于障礙一個個判斷繁瑣,想了一下只好用一個字符串表示元素的狀態了。
初始化:
</>復制代碼
@Override
public ArrayList> init(ArrayList> maze, int size, int obstacleNumber) {
// TODO Auto-generated method stub
//初始化起點
int startX = (int) (Math.random() * size);
int startY = (int)(Math.random() * size);
E start = (E)maze.get(startY).get(startX);
start.setStatus("start");
this.start = start;
//初始化終點
int endlX = 0;
int endlY = 0;
E end = null;
do {
endlX = (int) (Math.random() * size);
endlY = (int) (Math.random() * size);
end = (E)maze.get(endlY).get(endlX);
} while(end.equals(start));
end.setStatus("endl");
this.end = end;
//初始化障礙
int number = 0;
while(number < obstacleNumber) {
int obstacleX = (int) (Math.random() * size);
int obstacleY = (int) (Math.random() * size);
E obstacle = maze.get(obstacleY).get(obstacleX);
if (!obstacle.equals(start) && !obstacle.equals(end)) {
if (obstacle.getStatus() != null) {
if (obstacle.getStatus().equals("obstacle")) {
continue;
}
} else {
number++;
obstacle.setStatus("obstacle");
}
}
}
this.maze = maze;
this.size = size;
return maze;
}
初始化結果是這樣的:
雖然很丑,但是沒什么辦法,畢竟是控制臺輸出的。
接下來就是求迷宮的解了,因為每一個迷宮元素的求解步驟都一樣,所以寫了一個遞歸函數,主要就是向上下左右依次查看是否能“通路”,若能通,則跳到下一個元素在進行遞歸,若不通,則標記元素不可通,若到達迷宮尾或迷宮頭,則結束。照著這個想法寫,雖然中間出現了不夠細心的錯誤,但最后還是能寫出答案的。
迷宮求解:
</>復制代碼
@Override
public boolean getAnswer(E element) {
// TODO Auto-generated method stub
//若為最后一個結束
if (element.equals(end)) {return true;}
E next = element;
//向上移動
if ((next = this.move(element.getX(), element.getY() - 1)) != null && !next.equals(start) ) {
if (!next.equals(this.end)) {
next.setStatus("existen");
}
next.setRoute("向上");
if(this.getAnswer(next)) {return true;}
}
//向左移動
if ((next = this.move(element.getX() - 1, element.getY())) != null && !next.equals(start) ) {
next.setRoute("向左");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
//向下移動
if ((next = this.move(element.getX(), element.getY() + 1)) != null && !next.equals(start) ) {
next.setRoute("向下");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
//向右移動
if ((next = this.move(element.getX() + 1, element.getY())) != null && !next.equals(start)) {
next.setRoute("向右");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
if (!element.equals(start)) {
element.setStatus("noexisten");
element.setRoute(null);
}
return false;
}
最后:
還有的缺陷就是他不能找到最短的路徑,想來這個實現沒有頭緒,老師也不要求,就沒有嘗試了。還有當沒有答案時它也沒有提示,懶得寫了。
總結:這個作業還是挺有意思的,感覺是讓自己對棧和遞歸有了個認識把。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77246.html
摘要:本人郵箱歡迎轉載轉載請注明網址代碼已經全部托管有需要的同學自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經迷宮要如何找到正確的路徑呢用代碼又怎么實現帶著這些問題我們繼續往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現在有零 本人郵箱: 歡迎轉載,轉載請注明網址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...
摘要:更多關于的文章請戳這里您的留言意見是對我最大的支持我的文章列表 迷宮求解算法一直是算法學習的經典,實現自然也是多種多樣,包括動態規劃,遞歸等實現,這里我們使用窮舉求解,加深對棧的理解和應用 定義Position類用于存儲坐標點 起點坐標為(1,1),終點坐標為(8,8)地圖打印在最下面 class Position { private int px; private i...
摘要:對應迷宮數組為實現語言實現求解方塊類型方塊行號方塊列號上一個方塊在隊列中位置順序隊進隊順時針迷宮路徑如下運行結果應用圍住神經貓游戲使用寫的項目源碼下載體驗最后附上我喜歡的歌的英文翻譯心做 問題 給定一個M×N的迷宮圖,求一條從指定入口到出口的最短路徑.假設迷宮圖如圖所示(M=8, N=8) showImg(https://segmentfault.com/img/bVRjIk?w=26...
摘要:引言上回精讀手寫編譯器語法分析說到了如何利用函數實現語法分析時,留下了一個回溯問題,也就是存檔讀檔問題。更多討論討論地址是精讀手寫編譯器回溯如果你想參與討論,請點擊這里,每周都有新的主題,周末或周一發布。 1 引言 上回 精讀《手寫 SQL 編譯器 - 語法分析》 說到了如何利用 Js 函數實現語法分析時,留下了一個回溯問題,也就是存檔、讀檔問題。 我們把語法分析樹當作一個迷宮,有直線...
摘要:而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。新添加的或待刪除的元素都保存在棧的同一端,稱作棧頂,另一端就叫棧底。在棧里,新元素都靠近棧頂,舊元素都接近棧底。 前言 JavaScript是當下最流行的編程語言之一,它可以做很多事情: 數據可視化(D3.js,Three.js,Chart.js); 移動端應用(React Native,Weex,AppCan,Fl...
閱讀 1125·2021-10-09 09:43
閱讀 18564·2021-09-22 15:52
閱讀 1068·2019-08-30 15:44
閱讀 3059·2019-08-30 15:44
閱讀 3251·2019-08-26 14:07
閱讀 912·2019-08-26 13:55
閱讀 2572·2019-08-26 13:41
閱讀 3093·2019-08-26 13:29
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要