迷宮求解算法一直是算法學(xué)習(xí)的經(jīng)典，實(shí)現(xiàn)自然也是多種多樣，包括動態(tài)規(guī)劃，遞歸等實(shí)現(xiàn)，這里我們使用窮舉求解，加深對棧的理解和應(yīng)用。迷宮求解算法可以抽象為圖的遍歷問題。在圖的遍歷過程中通常由深度優(yōu)先遍歷（DFS）和廣度優(yōu)先遍歷（BFS）兩種。此例我們采用深度優(yōu)先遍歷，當(dāng)然，在不同的情景之下，不同的優(yōu)先遍歷算法執(zhí)行效率會有很大的差異，需要根據(jù)不同的使用環(huán)境選用合適的遍歷算法。
深度優(yōu)先遍歷
深度優(yōu)先遍歷從某個頂點(diǎn)出發(fā)，首先訪問這個頂點(diǎn)，然后找出剛訪問這個結(jié)點(diǎn)的第一個未被訪問的鄰結(jié)點(diǎn)，然后再以此鄰結(jié)點(diǎn)為頂點(diǎn)，繼續(xù)找它的下一個新的頂點(diǎn)進(jìn)行訪問，重復(fù)此步驟，直到所有結(jié)點(diǎn)都被訪問完為止。
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷從某個頂點(diǎn)出發(fā)，首先訪問這個頂點(diǎn)，然后找出這個結(jié)點(diǎn)的所有未被訪問的鄰接點(diǎn)，訪問完后再訪問這些結(jié)點(diǎn)中第一個鄰接點(diǎn)的所有結(jié)點(diǎn)，重復(fù)此方法，直到所有結(jié)點(diǎn)都被訪問完為止。
定義Position類用于存儲坐標(biāo)點(diǎn)
起點(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ù)
move函數(shù)分別向四個方向移動，然后將可行的path入棧.
注意，這里棧元素中每個棧元素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)前位置四個方向都走不通，則將當(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<String> footPrint;//足跡
private ArrayList<Position> test;
private MyStack<Position> 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ù)分別向四個方向移動，然后將可行的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)前位置四個方向都走不通，則將當(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("下面是足跡,長度是：" + 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();
}
}
Paste_Image.png
大家可能會疑惑，為什么足跡是不連續(xù)的（例如：21，12）兩個位置是走不通的，是因?yàn)樵趐ath遍歷過程中存在跳棧，既當(dāng)前位置走不通便會將當(dāng)前位置的Position出棧（stacks.pop），然后繼續(xù)上一節(jié)點(diǎn)遍歷。
更新：
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class Maze {
private Position startPosition;
private Position endPosition;
private HashMap<Integer,Integer> pathMap;
public Maze() {
startPosition = new Position(1,1);
endPosition = new Position(8,8);
pathMap = new HashMap<>();
}
private final int mazeZone[][] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,0,1,0,1},
{1,0,0,0,1,1,0,0,1,1},
{1,1,1,1,1,0,0,1,0,1},
{1,0,0,0,0,0,0,0,1,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,0,1,0,1,1,1,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
private class Position{
private int indexX;
private int indexY;
public Position(int indexX, int indexY) {
this.indexX = indexX;
this.indexY = indexY;
}
public int getIndexX() {
return indexX;
}
public int getIndexY() {
return indexY;
}
@Override
public boolean equals(Object obj) {
if (obj == null)return false;
Position temp=null;
if (obj instanceof Position) {
temp = (Position) obj;
}else {
return false;
}
if(temp.indexX == this.indexX && temp.indexY == this.indexY)return true;
else return false;
}
@Override
public int hashCode() {
return this.indexX*10+indexY;
}
@Override
public String toString() {
return "["+this.indexX+","+indexY+"]";
}
}
public void printMaze(){
for (int i = 0;i < mazeZone.length;i++){
for (int j = 0;j<mazeZone[0].length;j++){
if(mazeZone[i][j] == 1)System.out.print("\033[46;37;4m"+" "+"\033[0m");
else System.out.print(" ");
}
System.out.println();
}
}
public void startSearch(){
Queue<Position> searchQueue=new LinkedBlockingQueue<>();
HashSet<Position> visitedList=new HashSet<>();
searchQueue.add(startPosition);
visitedList.add(startPosition);
while (!searchQueue.isEmpty()){
Position currentPosition=searchQueue.poll();
int tempX=currentPosition.getIndexX();
int tempY=currentPosition.getIndexY();
if(tempX == endPosition.getIndexX() && tempY == endPosition.getIndexY()){
System.out.println("search finished! path has been detected!");
break;
}
//test move up
if(mazeZone[tempX-1][tempY]==0){
Position p=new Position(tempX-1,tempY);
if (visitedList.add(p)) {
searchQueue.add(p);
System.out.println("["+tempX+","+tempY+"]"+"->"+"["+(tempX-1)+","+tempY+"]");
pathMap.put(new Integer((tempX-1)*10+tempY),new Integer(tempX*10+tempY));
}
}
//test move down
if(mazeZone[tempX+1][tempY]==0){
Position p=new Position(tempX+1,tempY);
if (visitedList.add(p)) {
searchQueue.add(p);
System.out.println("["+tempX+","+tempY+"]"+"->"+"["+(tempX+1)+","+tempY+"]");
pathMap.put(new Integer((tempX+1)*10+tempY),new Integer(tempX*10+tempY));
}
}
//test move left
if(mazeZone[tempX][tempY-1]==0){
Position p=new Position(tempX,tempY-1);
if (visitedList.add(p)) {
searchQueue.add(p);
System.out.println("["+tempX+","+tempY+"]"+"->"+"["+tempX+","+(tempY-1)+"]");
pathMap.put(new Integer(tempX*10+tempY-1),new Integer(tempX*10+tempY));
}
}
//test move right
if(mazeZone[tempX][tempY+1]==0){
Position p=new Position(tempX,tempY+1);
if (visitedList.add(p)) {
searchQueue.add(p);
System.out.println("["+tempX+","+tempY+"]"+"->"+"["+tempX+","+(tempY+1)+"]");
pathMap.put(new Integer(tempX*10+tempY+1),new Integer(tempX*10+tempY));
}
}
}
int temp=pathMap.get(88);
System.out.print(88 + "<-");
while (temp != 11){
System.out.print(temp + "<-");
temp = pathMap.get(temp);
}
System.out.print(11);
System.out.println();
printMaze();
}
}
