寻路问题--如何找到一条从起点坐标到终点坐标的路径？

import java.util.ArrayList;
import java.util.HashMap;

public class FinaPath {
    
    private int[][] martix;
    
    private class Point{
        int x;//横坐标
        int y;//纵坐标
        
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public FinaPath(int[][] martix) {
        this.martix = martix;
    }
    
    //寻找起点(0,0)到终点(x,y)的一条路径
    public boolean findPath(int x, int y, ArrayList<Point> paths)
    {
        Point p = new Point(x, y);
        paths.add(p);//默认终点p的坐标对应的 数组值不是1
        
        //base condition
        if(x == 0 && y == 0)
            return true;
    
        boolean isSuccess = false;
        if(y >= 1 && checkFree(x, y - 1))
            isSuccess = findPath(x, y - 1, paths);
        if(!isSuccess && x >= 1 && checkFree(x - 1, y))
            isSuccess = findPath(x - 1, y, paths);
            
        if(!isSuccess)
            paths.remove(p);//O(N)
        return isSuccess;
    }
    
    private boolean checkFree(int x, int y){
        return martix[x][y] == 0;//0 表示有路
    }
    
    public boolean findPath_DP(int x, int y, ArrayList<Point> paths){
        //if dp[i][j]=true, exist at least one path from <i,j> to <x,y>(destination)
        boolean[][] dp = new boolean[x+1][y+1];//"状态矩阵"保存 各点的可达情况
//        //init
//        for(int i = x - 1; i >= 0; i--){
//            for(int j = y - 1; j >= 0; j--){
//                dp[i][j] = false;
//            }
//        }
        dp[x][y] = true;//init
        
        for(int i = x; i >= 0; i--){
            for(int j = y; j >= 0; j--){
                if(dp[i][j])//只有 从可达的点开始(初始时为终点)判断前面一个顶点是否可以到达本顶点
                {
                    if(i >= 1 && checkFree(i-1, j))
                        dp[i-1][j] = true;
                    if(j >= 1 && checkFree(i, j-1))
                        dp[i][j-1] = true;
                }
            }
        }
        
        /*
         * findPath recursively using dp "state martix"
         * 它是通过查表 而不是 递归调用 判断 从某个顶点到终点是否可达
         */
        return getPath(x, y, dp, paths);
    }
    private boolean getPath(int x, int y, boolean[][] dp, ArrayList<Point> paths){
        Point p = new Point(x, y);
        paths.add(p);
        
        if(dp[x][y] == false)//查表 判断 从<x,y>是否可达终点
            return false;

        //base condition
        if(x == 0 && y == 0)
            return true;
        
        boolean isSuccess = false;
        if(x >= 1 && (dp[x - 1][y] == true))
            isSuccess = getPath(x-1, y, dp, paths);
        if(!isSuccess && y >= 1 && dp[x][y-1] == true)
            isSuccess = getPath(x, y-1, dp, paths);
        if(!isSuccess)
            paths.remove(p);
        return isSuccess;
    }
    
    //另一种动态规划解决方案,它用HashMap缓存已经检查过的顶点
    public boolean findPath_dp2(int x, int y, ArrayList<Point> paths, HashMap<Point, Boolean> cache)
    {
        Point p = new Point(x, y);
        
        //先查表.
        if(cache.containsKey(p))
            return cache.get(p);
        
        paths.add(p);
        
        if(x == 0 && y == 0)
            return true;
        boolean isSuccess = false;
        if(x >= 1 && checkFree(x - 1, y))
            isSuccess = findPath_dp2(x - 1, y, paths, cache);
        if(!isSuccess && y >= 1 && checkFree(x, y - 1))
            isSuccess = findPath_dp2(x, y - 1, paths, cache);
        
        if(!isSuccess)
            paths.remove(p);
        cache.put(p, isSuccess);
        return isSuccess;
    }
    
    //test
    public static void main(String[] args) {
        
        //0表示有路,1表示障碍
        int[][] martix = {
            {0,0,1,1,0},
            {1,0,0,0,0},
            {0,1,0,0,0},
            {0,0,1,1,0},
            {0,1,0,0,0}
                };
        FinaPath fp = new FinaPath(martix);
        ArrayList<Point> paths = new ArrayList<FinaPath.Point>(martix.length + martix[0].length);
        int endPivot_x = 4;
        int endPivot_y = 4;
        boolean hasPath = fp.findPath(endPivot_x, endPivot_y, paths);
        if(hasPath)
            printPath(paths);
        else
            System.out.println("recursive finds no path");
        
        System.out.println();
        
        ArrayList<Point> paths_dp = new ArrayList<FinaPath.Point>();
        boolean hasPath_DP = fp.findPath_DP(endPivot_x, endPivot_y, paths_dp);
        if(hasPath_DP)
            printPath(paths_dp);
        else
            System.out.println("dp finds no path");
        
        System.out.println();
        
        ArrayList<Point> paths_dp2 = new ArrayList<FinaPath.Point>();
        HashMap<Point, Boolean> cache = new HashMap<FinaPath.Point, Boolean>(endPivot_y + endPivot_x);
        boolean hasPath_DP2 = fp.findPath_dp2(endPivot_x, endPivot_y, paths_dp2, cache);
        if(hasPath_DP2)
            printPath(paths_dp2);
        else
            System.out.println("dp2 finds no path");
    }
    private static void printPath(ArrayList<Point> paths){
        for(int i = paths.size() - 1; i >= 0; i--)
        {
            System.out.print("<" + paths.get(i).x + "," + paths.get(i).y + ">");
            System.out.print("  ");
        }
    }
}