福州seo网站推广优化,域名 网址 网站名称,网站建设播放vr视频教程,青岛城乡建筑设计院有限公司导读#xff1a;算法哥好久没分享有趣的算法题了#xff0c;有点寂寞空虚冷#xff0c;今天看到一道似曾相识的题目#xff0c;而且难度是hard模式#xff0c;勾起了算法哥的征服欲。特分享之#xff01;题目描述「推箱子」是一款风靡全球的益智小游戏#xff0c;玩家需…导读算法哥好久没分享有趣的算法题了有点寂寞空虚冷今天看到一道似曾相识的题目而且难度是hard模式勾起了算法哥的征服欲。特分享之题目描述「推箱子」是一款风靡全球的益智小游戏玩家需要将箱子推到仓库中的目标位置。游戏地图用大小为 m * n 的网格 grid 表示其中每个元素可以是墙、地板或者是箱子。现在你将作为玩家参与游戏按规则将箱子 B 移动到目标位置 T 玩家用字符 S 表示只要他在地板上就可以在网格中向上、下、左、右四个方向移动。地板用字符 . 表示意味着可以自由行走。墙用字符 # 表示意味着障碍物不能通行。箱子仅有一个用字符 B 表示。相应地网格上有一个目标位置 T。玩家需要站在箱子旁边然后沿着箱子的方向进行移动此时箱子会被移动到相邻的地板单元格。记作一次「推动」。玩家无法越过箱子。返回将箱子推到目标位置的最小 推动 次数如果无法做到请返回 -1。题目来源LeetCode 1263示例一题目分析其实这个题目一看就能想到需要用广度优先搜索算法(BFS)我们也很自然的会想到模拟推箱子的过程即可过程以箱子为起点尝试每一步4个方向移动移动的前提是人可以达到箱子移动过去的格子的反方向的格子所以这里还需要判断一下人从当前位置是否可以到达那个反方向的格子。至此题目的思路就出来了。在BFS的时候我们需要把搜索过的人和箱子的位置做一个标记防止重复搜索因为变化位置的只有可能是人的位置以及箱子的位置所以我们可以用一个四维数组来标记人和箱子的状态BFS过程中检查一下人和箱子的位置是不是以前搜索过搜索过就放弃反之就继续搜索!显然搜索的起点是初始状态下箱子和人的位置我们标记为(bx,by)和(sx,sy)初始移动次数是0然后我们从起点出发遍历箱子的4个方向检查是否可以推过去(推过去的格子是不是墙人是不是可以到达推过去格子反方向的格子)如果可以把新的箱子位置和人的位置以及推动箱子次数作为一个新的状态加入到BFS的队列里继续搜索直到走到位置T.源码如下源码复杂度分析运行时间空间复杂度首先我们搜索的时候是从人和箱子的位置来搜索的箱子的位置有m*n种人的位置也有m*n种但是实际在搜索过程中人永远在箱子相邻4个格子所以人的位置对于每个箱子位置是4个总的搜索状态是m*n*4的其次每次推动过程中有一次判断人的位置是否可以到达箱子推动方向反方向的格子的判断这个步骤是m*n的复杂度所以总的时间复杂度是O(m*n*m*n)的击败了100%的提交总结这个题目是一个比较经典的BFS算法的题目虽然比较容易想到但是实现起来是有一定难度的主要要解决以下几个问题想到模拟箱子推动的过程用BFS算法模拟知道根据箱子和人的位置来标记已经搜索过的状态两层BFS的嵌套使用外层BFS解决箱子搜索的问题里层BFS解决判断人是否可达到箱子推动反方向格子的问题一些编码上的技巧比如通过方向向量向4个方向搜索等题目分享完毕记得给算法哥点赞、分享、评论、转发哦这都是算法哥继续分享下去的最大鼓励
