小老鼠走進了格子迷宮，如何能繞過貓并以最短的路線吃到奶酪呢？
注意隻能上下左右移動，不能斜着移動。
在解決迷宮問題上，深度優先算法的思路是沿着一條路一直走，遇到障礙或走出邊界再傳回嘗試别的路徑。
首先用一個二維數組來把迷宮“數字化”。
int[][] maze = new int[5][4];
迷宮中每個格子的橫縱坐标對應數組的一維和二維索引，例如最左上角的格子是maze[0][0]，數組的值表示該格子是否可以通過，0表示可以通過，1表示該格子有貓。
初始化迷宮，标記貓的位置：
this.maze[2][0] = 1;
this.maze[1][2] = 1;
this.maze[2][2] = 1;
this.maze[3][2] = 1;
起點位置坐标是x=0，y=0，如果向右移動就是x=x+1,y=y，向下移動是x=x,y=y+1。我們預先規定每到一個格子都按照右、下、左、上的順序嘗試下一個格子是否能走，如果右邊的格子沒有貓且未出邊界，就移動到下一個格子，繼續按照右、下、左、上的順序嘗試；如果右邊的格子不能走則嘗試下面的格子。
下面這個二維數組用來周遊嘗試四個方向的格子：
int[][] next = new int[][] {
{1, 0},
{0, 1},
{-1, 0},
{0, -1}
};
為了不走回頭路，我們還需要另外一個二維數組标記哪些格子是已走過的，如果已走過則不能回頭。
int[][] mark = new int[5][4];
用一個棧記錄路徑
LinkedList<Integer> map = new LinkedList<>();
走格子的思路是：
for(周遊四個方向的格子) {
if(格子超出邊界 或 格子有貓 或 格子已經走過) {
continue;
} else {
移動到格子
記錄目前格子已走過
記錄目前路徑
for(以新格子為中心周遊四個方向的格子) {
......
}
}
}
但是我們并不知道要走多少步才能到達目标，也就不知道循環要嵌套多少層，但是可以看出每次新的周遊循環開啟後，執行的代碼和上一層循環是一樣的，是以這裡用遞歸解決。來看完整的代碼：
import java.util.LinkedList;
public class DfsRatMaze {
int min = Integer.MAX_VALUE;
int endX = 3; //目标點橫坐标
int endY = 3; //目标點縱坐标
int width = 5; //迷宮寬度
int height = 4; //迷宮高度
int[][] maze = new int[5][4];
int[][] mark = new int[5][4];
LinkedList<Integer> map = new LinkedList<>();
public void dfs(int startX, int startY, int step) {
int[][] next = new int[][] { //按右->下->左->上的順序嘗試
{1, 0},
{0, 1},
{-1, 0},
{0, -1}
};
int nextX, nextY;
int posible;
if(startX == endX && startY == endY) {
if(step < min)
min = step;
for(int i = map.size() - 1; i >= 0; i -= 2){
nextX = map.get(i);
nextY = map.get(i - 1);
System.out.print("[" + nextX + "," + nextY + "]");
if(i != 1)
System.out.print("->");
}
System.out.println();
return;
}
for(posible = 0; posible < next.length; posible++) { //按右->下->左->上的順序嘗試
nextX = startX + next[posible][0];
nextY = startY + next[posible][1];
if(nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) { //超出邊界
continue;
}
if(maze[nextX][nextY] == 0 && mark[nextX][nextY] == 0) { //非障礙且未标記走過
map.push(nextX);
map.push(nextY);
mark[nextX][nextY] = 1;
dfs(nextX, nextY, step + 1); //遞歸調用, 移動到下一格
mark[nextX][nextY] = 0;
map.pop();
map.pop();
}
}
}
/*
* 初始化迷宮
*/
public void initMaze() {
this.maze = new int[width][height];
this.mark = new int[width][height];
this.maze[2][0] = 1;
this.maze[1][2] = 1;
this.maze[2][2] = 1;
this.maze[3][2] = 1;
this.mark[0][0] = 1;
//列印迷宮 _表示可通行 *表示障礙 !表示目标
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
if(x == endX && y == endY) {
System.out.print("! ");
} else if(this.maze[x][y] == 1) {
System.out.print("* ");
} else {
System.out.print("_ ");
}
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
int startX = 0;
int startY = 0;
DfsRatMaze d = new DfsRatMaze();
d.initMaze();
d.dfs(startX, startY, 0);
if(d.min < Integer.MAX_VALUE)
System.out.println("最少需要" + d.min + "步");
else
System.out.println("目标地點無法到達");
}
}
運作後輸出：
[1,0]->[1,1]->[2,1]->[3,1]->[4,1]->[4,2]->[4,3]->[3,3]
[1,0]->[1,1]->[2,1]->[3,1]->[3,0]->[4,0]->[4,1]->[4,2]->[4,3]->[3,3]
[1,0]->[1,1]->[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[3,3]
[0,1]->[1,1]->[2,1]->[3,1]->[4,1]->[4,2]->[4,3]->[3,3]
[0,1]->[1,1]->[2,1]->[3,1]->[3,0]->[4,0]->[4,1]->[4,2]->[4,3]->[3,3]
[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[3,3]
最少需要6步
可以看到，程式計算出了所有路線，并找到了最短的路線。而整個代碼還不到100行，真是神奇的算法。