java學習深度優先算法

[Java]代碼    

package cn.xuhang.collection;

import java.util.ArrayList;
import java.util.List;

/**
 * 從一個點到達另一個點的路徑<br/>
 * 用到深度優先算法dfs<br/>
 * 
 * @author Hang
 *
 */
public class MazePath{
    public static List<Point> path = new ArrayList<Point>();
    public static List<List<Point>> pathes = new ArrayList<List<Point>>();
    public static int block = 0;//不可通過
    public static int access = 1;//可以通過
    public static int target = 9;//目標
    public static void main(String[] args) {
        int[][] grid = {{1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1},
                        {0,1,1,1,1,0,0,0,1,0,1,0,1,0,1,1,1},
                        {1,0,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1},
                        {1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0},
                        {1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0},
                        {1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1},
                        {1,0,1,1,0,0,0,1,9,0,0,1,1,1,0,0,1},
                        {1,0,1,0,0,1,0,1,1,0,0,0,1,1,1,0,1},
                        {1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0},
                        {1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0},
                        {1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,0},
                        {1,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1},
                        {0,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,1},
                        {1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1}};

        dfs(grid, new Point(0, 0), path);
        if(pathes.size() > 0){
            for(List<Point> posibility : pathes){
                System.out.println("============");
                System.out.println(posibility);
            }
        }
    }
    /**
     * 
     *      S * * * * <br/>
     *      * - * - - <br/>
     *      - - * - - <br/>
     *      * * * - - <br/>
     *      - * - * - <br/>
     *      * E * * - <br/>
     * 計算從S開始，沿著星號（*）前進，橫線（-）表示不可通過，到達E點的所有可行路徑。 <br/>
     * 這里使用了深度優先算法進行遍歷，從起點(0,0)開始，由于目標點所在的坐標在起點的右下方，所有優先遍歷右邊和下邊的點。 <br/>
     * 但是，這里也有例外，雖然目標點在起點右下方，但是在前進過程中仍然需要向左/上移動，比如： <br/>
     *      S - - - - <br/>
     *      * - * * * <br/>
     *      * - * - * <br/>
     *      * - E - * <br/>
     *      * - - - * <br/>
     *      * * * * * <br/>
     * 每個點出發有四個方向可以移動，如果超出邊界則不移動，移動到下一個點之后如果這個點表示不可通過（-）則返回false。<br/>
     * 每經過一個點，會先將其放入path列表中，表示該點已經走過，避免下一個點返回后重復造成死循環。比如A點向右移動到B點，B點可以向左移動到A點，
     * 重復此步驟會造成死循環。因此需要一個列表記錄所走過的點，同時，在遍歷完該點四個方向的點之后表示遞歸這個點及該點之后所有可行路徑結束，從
     * 列表中移除改點，從其他方向來的點可以繼續通過該點。
     *      * * -
     *      - A B
     *      - E F
     * 比如經過A點時，此時列表的變化依次是
     * [*,*,A]→[*,*,A,E]→[*,*,A,E,F]→[*,*,A,E,F,B]→[*,*,A,E,F]→[*,*,A,E]→
     * [*,*,A]→[*,*,A,B]→[*,*,A,B,F]→[*,*,A,B,F,E]→[*,*,A,B,F]→[*,*,A,B]→[*,*,A]→[*,*]
     * 
     * path列表用來防止重復走過的點造成死循環，參數path0用來記錄從起點開始到達每一個點之前的完整路徑。
     * 
     * @param grid 陣圖，一個二維數組，用不同的符號表示哪些點可以通過，哪些點不能通過，哪些點是目標所在的位置
     * @param point 當前坐標，這里將坐標包裝成Point對象，對象有x,y兩個屬性，分別表示在二維數組中的位置
     * @param path0 路徑，表示從起點開始，到達這個點之前所經過的點的集合
     * @return 表示這個點是否可以繼續往下走，這里獲取可行的路徑{@link pathes}是主要目的，返回值沒有太大作用
     */
    public static boolean dfs(int[][] grid, Point point, List<Point> path0){

        List<Point> p = new ArrayList<Point>();
        p.addAll(path0);
        p.add(point);//拷貝上一個點經過的路徑，并接著上一個點的路徑繼續

        if(grid[point.x][point.y] == 9){//到達
            pathes.add(p);
            return true;
        }

        if(grid[point.x][point.y] != 0 && !path.contains(point)){//這個點可以走(1和9) 并且 未走過
            path.add(point);//現在走point
            if(point.x + 1 <= grid.length-1){
                dfs(grid, point.down(), p);                     //往下
            }
            if(point.y + 1 <= grid[point.x].length-1){
                dfs(grid, point.right(), p);                    //往右
            }
            if(point.x - 1 >= 0){
                dfs(grid, point.up(), p);                       //往上
            }
            if(point.y - 1 >= 0){
                dfs(grid, point.left(), p);                     //往左
            }
            path.remove(point);//走過point，之后從其他點過來的也能繼續走
        }
        //如果不可走(0) 或者 已走過
        return false;
    }


    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        Point left(){
            return new Point(x, y-1);
        }
        Point right(){
            return new Point(x, y+1);
        }
        Point up(){
            return new Point(x-1, y);
        }
        Point down(){
            return new Point(x+1, y);
        }

        public String printDirection(Point nextPoint){
            String direction = null;
            if(nextPoint == null){
                direction = "●";
            }else{
                if(this.x == nextPoint.x){
                    direction = (this.y < nextPoint.y) ? "→" : "←";
                }
                if(this.y == nextPoint.y){
                    direction = (this.x < nextPoint.x) ? "↓" : "↑";
                }
            }
            return direction;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        };
        @Override
        public boolean equals(Object obj){
            Point p = (Point) obj;
            if(p.x == this.x && p.y == this.y){
                return true;
            }else{
                return false;
            }
        }
        @Override
        public String toString() {
            return "(" + this.x + "," + this.y +")";
        }
    }
}