【算法】动态规划 ⑥ ( 骑士的最短路径 II | 问题分析 | 代码示例 )

class Solution {

    // 根据骑士只能向右的四个方向 , 走到 (i, j) 点的最短路径, 需要依赖
    // ( i + 2 , j - 1 )
    // ( i + 1 , j - 2 )
    // ( i - 1 , j - 2 )
    // ( i - 2 , j - 1 )
    // 四个点的最短路径, 将上述累加值保存到数组中, 用于快速找到依赖点
    public static int[] deltaX = {2, 1, -1, -2};
    public static int[] deltaY = {-1, -2, -2, -1};

    public int shortestPath2(int[][] obstacleGrid) {
        // 验证函数参数
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }

        // 1. 动态规划状态 State
        // dp[i][j] 表示 从 (0, 0) 位置出发 , 到 (i, j) 位置的方案总数 ;
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        // 2. 动态规划初始化 Initialize
        // 还没开始跳, 此时先将所有的点的状态值设置为 Integer.MAX_VALUE
        // 含义是 所有的点 都无法跳到 , 需要跳无数次才能跳到
        // 但是 (0, 0) 点除外, 其本身跳到本身路径数为 0
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;

        // 3. 动态规划方程 Function
        // 运动时 , 只能向 右侧的 四个日字方向走
        // ① 纵坐标方向上 i 减少 2 行 , 横坐标方向上 j 增加 1 列 ;
        // ② 纵坐标方向上 i 减少 1 行 , 横坐标方向上 j 增加 2 列 ;
        // ③ 纵坐标方向上 i 增加 1 行 , 横坐标方向上 j 增加 2 列 ;
        // ④ 纵坐标方向上 i 增加 2 行 , 横坐标方向上 j 增加 1 列 ;
        // 从这四个方向中 , 找出路径最小的方向即可
        // 如果遇到障碍物 , 则需要 continue 跳过本次计算 , 继续执行下一次计算 ;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 遇到障碍物 , 跳过
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }

                // 遍历依赖的四个方向
                for (int d = 0; d < 4; d++) {
                    int x = i + deltaX[d];
                    int y = j + deltaY[d];

                    // 判断 x, y 是否超出边界
                    if (x < 0 || x >= n || y < 0 || y >= m) {
                        continue;
                    }

                    // 判断当前位置是否可达, 如果为无穷大 , 说明不可达
                    if (dp[x][y] == Integer.MAX_VALUE) {
                        continue;
                    }

                    // 取当前依赖路径的最小值作为最终的 最小路径数
                    dp[i][j] = Math.min(dp[i][j], dp[x][y] + 1);
                }
            }
        }

        // 4. 动态规划答案 Answer
        if (dp[m - 1][n - 1] == Integer.MAX_VALUE) {
            System.out.println("终点不可达");
            return -1;
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        // 1 的位置是障碍物
        int[][] obstacleGrid = {{0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0}};
        int result = new Solution().shortestPath2(obstacleGrid);
        System.out.println("最短路径数为 " + result);
    }
}

最短路径数为 2