回溯法解決迷宮求解問題

一、迷宮求解問題

如下圖小球在起點(1,1)需要移動到終點(6,5),求能否順利到達終點，若能，路徑是什麼。

下圖即為采用 下->右->上->左的政策得出的結果。

二、解決思路

用二維數組map存放小地圖，其中，

• 如果元素為0，則為未走過的空閑節點
• 如果元素為1，則表示為牆
• 如果元素為2，表示可以走
• 如果元素為3，說明走過該路，此路不通

1. 如果該元素為0，假設該點可以走通，則按照下、右、上、左的政策依次判斷能否走通，如果可以走通，則繼續走，直到走不通為止，然後進行回溯
2. 如果終點為2，說明已經找到路徑，終止遞歸。

三、代碼實作

/**
 * @author ymy
 * @date 2020/5/12
 * 迷宮求解問題 的 遞歸實作
 */
public class MazeSolver {

    public  static void  main(String [] args){
        MazeSolver ms = new MazeSolver();
        ms.test();
    }

    public void test(){
        int rows=8;
        int cols=7;
        int [][] map = new int [rows][cols];//地圖
        createMap(rows,cols,map);
        displayArray(map);
        System.out.println("-------");
        getWay(map,1,1);
        displayArray(map);
    }

    /**
     *
     * @param map 地圖
     * @param i  起點橫坐标
     * @param j  起點縱坐标
     * @return  是否找到得到位置
     *
     * 1.如果小球從起點能找到終點，則證明通路找到
     * 2.約定：當地圖(i,j)為0時則沒走過，若為1時，表示障礙物，如果為2表示走過
     * 3.若該位置為3，則此路不通。
     * 4.政策嘗試順序，下->右->上->左，若路徑不通，則回溯
     */
    public boolean getWay(int [][]map,int i,int j){
        if(map[6][5]==2){
            return true;
        }else if(map[i][j]==0){
            map[i][j]=2;
            if (getWay(map,i+1,j)){
                return true;
            }else if (getWay(map,i,j+1)){
                return  true;
            }else if(getWay(map,i-1,j)){
                return true;
            }else if(getWay(map,i,j-1)){
                return true;
            }else {
                map[i][j]=3;
                return false;
            }
        }else {
            return false;
        }
    }

    public void createMap(int rows,int cols,int [][] map){
    //設定障礙
        for (int i = 0; i <cols; i++) {
            map[0][i]=1;
            map[rows-1][i]=1;
        }
        for(int i =0;i<rows;i++){
            map[i][0]=1;
            map[i][cols-1]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        map[5][3]=1;
        map[5][4]=1;
        map[5][5]=1;
    }

    public void displayArray(int [][] array){
        for (int[] ints : array) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
    }
}
           

四、測試