摘要：這周數(shù)據(jù)結(jié)構(gòu)老師布置了一個作業(yè)，用棧來實現(xiàn)迷宮的求解，本來是要求自己寫一個棧的類來實現(xiàn)，但是自己懶得寫了，因為遞歸也是棧的一種實現(xiàn)，就直接用了遞歸來寫。
這周數(shù)據(jù)結(jié)構(gòu)老師布置了一個作業(yè)，用棧來實現(xiàn)迷宮的求解，本來是要求自己寫一個棧的類來實現(xiàn)，但是自己懶得寫了，因為遞歸也是棧的一種實現(xiàn)，就直接用了遞歸來寫。
迷宮求解，主要用的是窮舉法:從起始位置開始，向東南西北四個方向每個方向都嘗試走，在每一個嘗試中，若可通，則納入當(dāng)前路徑，將下一位置切換為當(dāng)前位置，再開始進(jìn)行嘗試，直到到達(dá)出口。若不可通，應(yīng)回退到前一個通快，除去嘗試過的方向再探索，四個方塊都不可通，則刪除當(dāng)前的通道塊,這個后進(jìn)先出的操作，可以用棧來實現(xiàn)，當(dāng)然也能用遞歸實現(xiàn)。
我想的是，迷宮應(yīng)該有四個方法:
1.隨機初始化迷宮(設(shè)置起點，終點，障礙)
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);//移動迷宮元素
}
在給迷宮初始化的時候遇到了問題，不能夠設(shè)置相同的起點和終點，不能設(shè)置相同的障礙，不能給起點和終點設(shè)置障礙。對于起點和終點，判斷一下就可以了，但是對于障礙一個個判斷繁瑣，想了一下只好用一個字符串表示元素的狀態(tài)了。
初始化:
@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;
}
初始化結(jié)果是這樣的:
雖然很丑，但是沒什么辦法，畢竟是控制臺輸出的。
接下來就是求迷宮的解了，因為每一個迷宮元素的求解步驟都一樣，所以寫了一個遞歸函數(shù)，主要就是向上下左右依次查看是否能“通路”，若能通，則跳到下一個元素在進(jìn)行遞歸，若不通，則標(biāo)記元素不可通，若到達(dá)迷宮尾或迷宮頭，則結(jié)束。照著這個想法寫，雖然中間出現(xiàn)了不夠細(xì)心的錯誤，但最后還是能寫出答案的。
迷宮求解:
@Override
public boolean getAnswer(E element) {
// TODO Auto-generated method stub
//若為最后一個結(jié)束
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;
}
最后:
還有的缺陷就是他不能找到最短的路徑，想來這個實現(xiàn)沒有頭緒，老師也不要求，就沒有嘗試了。還有當(dāng)沒有答案時它也沒有提示，懶得寫了。
總結(jié):這個作業(yè)還是挺有意思的，感覺是讓自己對棧和遞歸有了個認(rèn)識把。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/77246.html
