【算法】动态规划 ⑥ ( 骑士的最短路径 II | 问题分析 | 代码示例 )
创始人
2024-04-21 11:39:14
0

文章目录

  • 一、问题分析
  • 二、代码示例


骑士的最短路径 II :


在 国际象棋 中 , 骑士 类似 与 象棋 中的 马 , 走 " 日 " 字 格子 ;

骑士有 8 种走法 : " 日 " 字 格子 , 参考 百度百科

  • 左走一格向前走两格
  • 左走一格向后走两格
  • 左走两格向前走一格
  • 左走两格向后走一格
  • 右走一格向前走两格
  • 右走一格向后走两格
  • 右走两格向前走一格
  • 右走两格向后走一格

下图是 骑士 的走法 , 黑色是 骑士的初始位置 ( 0 , 0 ) , 绿色 和 红色 是 骑士 可以走的 下一步位置 ;
在这里插入图片描述


给定一个二维坐标 , 在该坐标系中 , 骑士只能走 上图中 右边 红色的四个方向的步骤 , 计算从 左上角 到 右下角 的最短路径数 ;





一、问题分析



如果 骑士 可以走 8 个方向 ,

  • 那么需要 使用 BFS 宽度优先搜索 算法 ;
  • 此时 不能使用 动态规划解决上述问题 , 如果 可以走 8 个方向 , 那么路径就可以反复 , 会出现 循环依赖的情况 ;

如果 骑士 只能走右边的 4 个方向 , 没有循环依赖 , 则可以使用动态规划 , 解决上述问题 ;


如果 骑士 只能走 右侧的 四个方向 , 也就是

  • 从 黑点 走到 红点 1 , 纵坐标方向上 i 减少 2 行 , 横坐标方向上 j 增加 1 列 ;
  • 从 黑点 走到 红点 2 , 纵坐标方向上 i 减少 1 行 , 横坐标方向上 j 增加 2 列 ;
  • 从 黑点 走到 红点 3 , 纵坐标方向上 i 增加 1 行 , 横坐标方向上 j 增加 2 列 ;
  • 从 黑点 走到 红点 4 , 纵坐标方向上 i 增加 2 行 , 横坐标方向上 j 增加 1 列 ;

在这里插入图片描述

那么 如果当前位置是 ( i , j ) , 那么当前位置的 最短路径 是 dp[i][j] , 那么该点的 最短路径 依赖于 如下几个点的最短路径 :

  • ( i + 2 , j - 1 ) , 对应 从 黑点 走到 红点 1 , 纵坐标方向上 i 减少 2 行 , 横坐标方向上 j 增加 1 列 ;
  • ( i + 1 , j - 2 ) , 对应 从 黑点 走到 红点 2 , 纵坐标方向上 i 减少 1 行 , 横坐标方向上 j 增加 2 列 ;
  • ( i - 1 , j - 2 ) , 对应 从 黑点 走到 红点 3 , 纵坐标方向上 i 增加 1 行 , 横坐标方向上 j 增加 2 列 ;
  • ( i - 2 , j - 1 ) , 对应 从 黑点 走到 红点 4 , 纵坐标方向上 i 增加 2 行 , 横坐标方向上 j 增加 1 列 ;

初始化状态值时 , 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

相关内容

热门资讯

鸿蒙怎样还原安卓系统,系统切换... 你有没有想过,鸿蒙系统竟然能还原安卓系统?这听起来是不是有点像魔法一样神奇?没错,今天就要带你一探究...
电脑安卓转苹果系统,系统迁移攻... 你有没有想过,有一天你的安卓手机突然变成了苹果的忠实粉丝,想要跳槽到iOS的阵营呢?这可不是什么天方...
安卓xp系统下载地址,轻松获取... 你有没有想过,手机系统也能穿越时空?没错,今天我要给你揭秘的就是这样一个神奇的存在——安卓XP系统。...
安卓系统怎么清理相册,安卓系统... 手机里的相册是不是越来越臃肿了?每次打开都感觉像是在翻山越岭,找一张照片都要费老鼻子劲。别急,今天就...
安卓系统安装ios转移,轻松实... 你有没有想过,手机系统之间的转换竟然也能如此神奇?没错,今天就要来聊聊安卓系统安装iOS转移这个话题...
安卓系统与ios系统的优势,系... 你有没有想过,为什么你的手机里装的是安卓系统而不是苹果的iOS系统呢?或者反过来,为什么你的朋友用的...
安卓系统游戏如何升级,轻松实现... 亲爱的安卓玩家们,你是否也和我一样,对安卓系统游戏升级这件事充满了好奇和期待呢?每次游戏更新,都仿佛...
安卓系统蛋仔派对,安卓系统下的... 你有没有发现,最近你的手机里多了一个超级好玩的游戏?没错,就是安卓系统上的“蛋仔派对”!这款游戏可是...
坚果3安卓原生系统,深度体验原... 你有没有听说过坚果3这款手机?它可是最近在数码圈里火得一塌糊涂呢!今天,我就要来给你详细介绍一下这款...
安卓子系统点不开,排查与解决指... 最近是不是你也遇到了安卓子系统点不开的烦恼?这可真是让人头疼啊!别急,今天就来给你详细解析一下这个问...
安卓系统经常误删文件,如何有效... 你有没有遇到过这种情况?手机里的文件突然不见了,找来找去,怎么也找不到。别急,这可能是安卓系统的小调...
安卓51系统如何破解,轻松解锁... 安卓51系统如何破解——探索未知的技术边界在数字化时代,手机已经成为我们生活中不可或缺的一部分。而安...
安卓系统怎么换回主题,安卓系统... 亲爱的手机控们,你是不是也和我一样,对安卓系统的主题换换换乐此不疲呢?不过,有时候换着换着,突然发现...
黑莓安卓系统 太垃圾,令人失望... 你有没有用过黑莓的安卓系统?别告诉我你没有,因为现在这个系统真的是太垃圾了!是的,你没听错,就是那个...
修改安卓系统权限代码,安卓系统... 你有没有想过,你的安卓手机里那些神秘的系统权限代码?它们就像隐藏在手机里的秘密通道,有时候让你觉得既...
虚拟大师安卓系统教程,教程详解... 你有没有想过,手机里的世界可以变得更加神奇?今天,就让我带你一起探索虚拟大师安卓系统的奥秘吧!想象你...
基于安卓系统个人博客,轻松构建... 你有没有想过,在这个信息爆炸的时代,拥有一片属于自己的网络小天地是多么酷的事情啊!想象每天都能在这里...
安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...