骑士的最短路径 II :
在 国际象棋 中 , 骑士 类似 与 象棋 中的 马 , 走 " 日 " 字 格子 ;
骑士有 8 种走法 : " 日 " 字 格子 , 参考 百度百科
下图是 骑士 的走法 , 黑色是 骑士的初始位置 ( 0 , 0 ) , 绿色 和 红色 是 骑士 可以走的 下一步位置 ;
给定一个二维坐标 , 在该坐标系中 , 骑士只能走 上图中 右边 红色的四个方向的步骤 , 计算从 左上角 到 右下角 的最短路径数 ;
如果 骑士 可以走 8 个方向 ,
如果 骑士 只能走右边的 4 个方向 , 没有循环依赖 , 则可以使用动态规划 , 解决上述问题 ;
如果 骑士 只能走 右侧的 四个方向 , 也就是
那么 如果当前位置是 ( i , j ) , 那么当前位置的 最短路径 是 dp[i][j] , 那么该点的 最短路径 依赖于 如下几个点的最短路径 :
初始化状态值时 , dp[i][j] 代表了从 起始点 ( 0 , 0 ) 位置 跳转到 ( i , j ) 位置的 最短路径数 ;
该算法求的是 最短路径数 , 初始化 状态 值 时 , 不能初始化为 0 , 这里 初始化为 Integer.MAX_VALUE 值 , 如果值为 Integer.MAX_VALUE 说明该点走不到 ;
如果 算法求的是 方案数 , 则初始化状态值时 , 可以初始化为 0 ;
代码示例 :
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) 点除外, 其本身跳到本身路径数为 0for (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. 动态规划答案 Answerif (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