求解迷宮（x,y），向上走，向右走，向下走，向左走……遞歸繼續求解。
深度優先遍歷
//走迷宮邏輯核心
private static final int d[][] = {{-1,0},{0,1},{1,0},{0,-1}};//四個方向
// 從(x,y)的位置開始求解迷宮，如果求解成功，返回true；否則返回false
private boolean go(int x, int y){
if(!data.inArea(x,y))
throw new IllegalArgumentException("x,y are out of index in go function!");
data.visited[x][y] = true;
setData(x, y, true);
if(x == data.getExitX() && y == data.getExitY())
return true;
for(int i = 0 ; i < 4 ; i ++){
int newX = x + d[i][0];
int newY = y + d[i][1];
if(data.inArea(newX, newY) &&
data.getMaze(newX,newY) == MazeData.ROAD &&
!data.visited[newX][newY])
if(go(newX, newY))
return true;
}
// 回溯
setData(x, y, false);
return false;
}
遞歸修改為非遞歸，用棧的數據結構。
private void run(){
setData(-1, -1, false);
Stack
stack = new Stack (); //構造棧 Position entrance = new Position(data.getEntranceX(), data.getEntranceY());
stack.push(entrance);
data.visited[entrance.getX()][entrance.getY()] = true;
boolean isSolved = false;
while(!stack.empty()){
Position curPos = stack.pop();
setData(curPos.getX(), curPos.getY(), true);
if(curPos.getX() == data.getExitX() && curPos.getY() == data.getExitY()){
isSolved = true;
findPath(curPos);
break;
}
for(int i = 0 ; i < 4 ; i ++){
int newX = curPos.getX() + d[i][0];
int newY = curPos.getY() + d[i][1];
if(data.inArea(newX, newY)
&& !data.visited[newX][newY]
&& data.getMaze(newX, newY) == MazeData.ROAD){
stack.push(new Position(newX, newY, curPos)); //增加一個curPos，記錄前一節點。
data.visited[newX][newY] = true;
}
}
}
if(!isSolved)
System.out.println("The maze has no Solution!");
setData(-1, -1, false);
}
廣度優先遍歷
利用隊列數據結構
private void run(){
setData(-1, -1, false);
LinkedList
queue = new LinkedList (); Position entrance = new Position(data.getEntranceX(), data.getEntranceY());
queue.addLast(entrance);
data.visited[entrance.getX()][entrance.getY()] = true;
boolean isSolved = false;
while(queue.size() != 0){
Position curPos = queue.pop();
setData(curPos.getX(), curPos.getY(), true);
if(curPos.getX() == data.getExitX() && curPos.getY() == data.getExitY()){
isSolved = true;
findPath(curPos);
break;
}
for(int i = 0 ; i < 4 ; i ++){
int newX = curPos.getX() + d[i][0];
int newY = curPos.getY() + d[i][1];
if(data.inArea(newX, newY)
&& !data.visited[newX][newY]
&& data.getMaze(newX, newY) == MazeData.ROAD){
queue.addLast(new Position(newX, newY, curPos));
data.visited[newX][newY] = true;
}
}
}
if(!isSolved)
System.out.println("The maze has no Solution!");
setData(-1, -1, false);
}
在多個解的情況下，廣度優先遍歷求的是最短解。
對棧和隊列你是否有了新的理解呢？
需要完整代碼及演示，請關注學點乾貨，點贊並轉發本文後私信乾貨菌獲取。
閱讀更多 學點乾貨 的文章
